{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Distinct Islands"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #hash-table #hash-function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #哈希表 #哈希函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numDistinctIslands"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不同岛屿的数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个非空 01 二维数组表示的网格，一个岛屿由四连通（上、下、左、右四个方向）的 <code>1</code> 组成，你可以认为网格的四周被海水包围。</p>\n",
    "\n",
    "<p>请你计算这个网格中共有多少个形状不同的岛屿。两个岛屿被认为是相同的，当且仅当一个岛屿可以通过平移变换（不可以旋转、翻转）和另一个岛屿重合。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/05/01/distinctisland1-1-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]\n",
    "<b>输出：</b>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]\n",
    "<b>输出</b><strong>:</strong> 3</pre>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/05/01/distinctisland1-2-grid.jpg\" /></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 50</code></li>\n",
    "\t<li><code>grid[i][j]</code>&nbsp;仅包含&nbsp;<code>0</code>&nbsp;或&nbsp;<code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-distinct-islands](https://leetcode.cn/problems/number-of-distinct-islands/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-distinct-islands](https://leetcode.cn/problems/number-of-distinct-islands/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]', '[[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        shape=set()\n",
    "\n",
    "        def check(arr):\n",
    "            n=len(arr)\n",
    "            dis=0\n",
    "            for i in range(n-1):\n",
    "                for j in range(i+1,n):\n",
    "                    x,y=arr[i]\n",
    "                    x1,y1=arr[j]\n",
    "                    dis=dis+((x-x1)**2+(y-y1)**2)**(0.5)\n",
    "            f=0\n",
    "            for x in shape:\n",
    "                if abs(x-dis)<=0.00001:\n",
    "                    f=1\n",
    "                    break\n",
    "            if f==0:\n",
    "                shape.add(dis)\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    tmp=[]\n",
    "                    grid[i][j]=0\n",
    "                    stack=collections.deque()\n",
    "                    stack.append([i,j])\n",
    "                    while stack:\n",
    "                        x,y=stack.popleft()\n",
    "                        tmp.append([x,y])\n",
    "                        for x1,y1 in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                            if 0<=x1<m and 0<=y1<n and grid[x1][y1]==1:\n",
    "                                grid[x1][y1]=0\n",
    "                                stack.append([x1,y1])\n",
    "                    check(tmp)\n",
    "        return len(shape)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        s=set()\n",
    "        ans=0\n",
    "        ls=[]\n",
    "        d=[[1,0],[0,1],[0,-1],[-1,0]]\n",
    "        def dfs(x,y):\n",
    "            if x<0 or y<0 or x>=m or y>=n:\n",
    "                return \n",
    "            if grid[x][y]==0:\n",
    "                return\n",
    "            grid[x][y]=0\n",
    "            ls.append((x,y)) \n",
    "            for dx,dy in d:\n",
    "                dfs(x+dx,y+dy)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    ls=[]\n",
    "                    dfs(i,j)\n",
    "                    now=0\n",
    "                    for a,b in ls:\n",
    "                        for aa,bb in ls:\n",
    "                            now+=((a-aa)**2+(b-bb)**2)**0.5\n",
    "                    now=round(now,5)\n",
    "                    if now in s:\n",
    "                        continue \n",
    "                    else:\n",
    "                        ans+=1\n",
    "                        s.add(now)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m, n, dc, alhas, res = len(grid), len(grid[0]), {}, set(), 0\n",
    "        def find(x):\n",
    "            if x not in dc: dc[x] = x\n",
    "            elif dc[x] != x: dc[x] = find(dc[x])\n",
    "            return dc[x]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    key = (i,j)\n",
    "                    dc[key] = key\n",
    "                    if i > 0 and grid[i-1][j]:\n",
    "                        dc[key] = find((i-1,j))\n",
    "                        if j > 0 and grid[i][j-1]:\n",
    "                            dc[find((i,j-1))] = dc[key]\n",
    "                    if j > 0 and grid[i][j-1]:\n",
    "                        dc[key] = find((i,j-1))\n",
    "        ss = defaultdict(list)\n",
    "        for i,v in dc.items():\n",
    "            ss[find(v)].append(i)\n",
    "        for lis in ss.values():\n",
    "            x0, y0 = lis[0]\n",
    "            x1, y1 = lis[0]\n",
    "            for i,j in lis:\n",
    "                x0, y0, x1, y1 = min(x0,i), min(y0,j), max(x1,i), max(y1,j)\n",
    "            POS = [[0,0,1,0,0,1],[0,x1-x0,0,1,-1,0],[x1-x0,y1-y0,-1,0,0,-1],[y1-y0,0,0,-1,1,0],[0,0,0,1,1,0],[0,y1-y0,1,0,0,-1],[y1-y0,x1-x0,0,-1,-1,0],[x1-x0,0,-1,0,0,1]]\n",
    "            has = [[] for _ in range(8)]\n",
    "            # print(x1,y1)\n",
    "            for i,j in lis:\n",
    "                ni, nj = i - x0, j - y0\n",
    "                for k in range(8):\n",
    "                    x, y, dxx, dxy, dyx, dyy = POS[k]\n",
    "                    has[k].append((x+ni*dxx+nj*dxy,y+ni*dyx+nj*dyy))\n",
    "            # print(has)\n",
    "            if tuple(has[0]) not in alhas:\n",
    "                res += 1\n",
    "                for i in has:\n",
    "                    alhas.add(tuple(sorted(i)))\n",
    "            # print(alhas)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        def dfs(r,c):\n",
    "            if 0<=r<m and 0<=c<n and grid[r][c]==1:\n",
    "                # flooding it to avoid visit it again\n",
    "                grid[r][c]=0\n",
    "                shape.add(complex(r,c))\n",
    "                dfs(r+1,c)\n",
    "                dfs(r-1,c)\n",
    "                dfs(r,c-1)\n",
    "                dfs(r,c+1)\n",
    "        def standardize(shape:set):\n",
    "            # trans表示对一个形状list进行归一化处理，得到一个sorted list，里面是每个点的相对矩形左上角的坐标，是一个归一化的过程\n",
    "            def trans(shape:set):\n",
    "                tl=complex(min(z.real for z in shape),min(z.imag for z in shape))\n",
    "                return sorted(str(z-tl) for z in shape)\n",
    "                \n",
    "            ans=[]\n",
    "            for k in range(4):\n",
    "                # (a+bj)*j表示一次顺时针旋转\n",
    "                # (a+bj)->(-b+aj)->(-a-bj)->(b-aj)\n",
    "                ans=max(ans,trans([z*(1j)**k for z in shape]))\n",
    "                # 由于所有的旋转过后的点的x-y对称也要考虑，因此还有其他四个点\n",
    "                # (b+aj)->(-a+bj)->(-b-aj)->(a-bj)\n",
    "                ans=max(ans,trans([complex(z.imag,z.real)*(1j)**k for z in shape]))\n",
    "            return tuple(ans)\n",
    "\n",
    "        shapes=set()\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                shape=set()\n",
    "                # 结果会被放进shape\n",
    "                dfs(r,c)\n",
    "                # 然后对这个结果产生8个不同的变换，选出最大的变换\n",
    "                if shape:\n",
    "                    shapes.add(standardize(shape))\n",
    "        return len(shapes)\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(i, j):\n",
    "            if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != 1:\n",
    "                return \n",
    "            shape.append(complex(i, j))\n",
    "            grid[i][j] = 0\n",
    "            dfs(i - 1, j)\n",
    "            dfs(i, j - 1)\n",
    "            dfs(i + 1, j)\n",
    "            dfs(i, j + 1)\n",
    "        def standardize(shape):\n",
    "            def transform(shape):\n",
    "                s = complex(min(s.real for s in shape), min(s.imag for s in shape))\n",
    "                return sorted(str(z - s) for z in shape)\n",
    "            res = []\n",
    "            for i in range(4):\n",
    "                res = max(res, transform([s * (1j) ** i for s in shape]))\n",
    "                res = max(res, transform([complex(s.imag, s.real) * (1j) ** i for s in shape]))\n",
    "            return tuple(res)\n",
    "        res = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    shape = []\n",
    "                    dfs(i, j)\n",
    "                    res.add(standardize(shape))\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        pos=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        # 遍历连通区域\n",
    "        def dfs(x,y):\n",
    "            vis.add((x,y))\n",
    "            grid[x][y]=0\n",
    "            for dx,dy in pos:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if 0<=xx<m and 0<=yy<n and grid[xx][yy]==1:\n",
    "                    dfs(xx,yy)\n",
    "        # 计算哈希值\n",
    "        def hashcode():\n",
    "            s=0\n",
    "            arr=list(vis)\n",
    "            k=len(arr)\n",
    "            dist=0\n",
    "            for i in range(k):\n",
    "                x,y=arr[i]\n",
    "                for j in range(i+1,k):\n",
    "                    a,b=arr[j]\n",
    "                    dist+=((x-a)**2+(y-b)**2)**0.5\n",
    "            for ca in candi:\n",
    "                if abs(dist-ca)<1e-5:\n",
    "                    break\n",
    "            else:\n",
    "                candi.add(dist)\n",
    "\n",
    "        vis=set()\n",
    "        candi=set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    dfs(i,j)\n",
    "                    hashcode()\n",
    "                    vis.clear()\n",
    "        \n",
    "        return len(candi)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(i, j):\n",
    "            if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != 1:\n",
    "                return \n",
    "            shape.append(complex(i, j))\n",
    "            grid[i][j] = 0\n",
    "            dfs(i - 1, j)\n",
    "            dfs(i, j - 1)\n",
    "            dfs(i + 1, j)\n",
    "            dfs(i, j + 1)\n",
    "        def standardize(shape):\n",
    "            def transform(shape):\n",
    "                s = complex(min(s.real for s in shape), min(s.imag for s in shape))\n",
    "                return sorted(str(z - s) for z in shape)\n",
    "            res = []\n",
    "            for i in range(4):\n",
    "                res = max(res, transform([s * (1j) ** i for s in shape]))\n",
    "                res = max(res, transform([complex(s.imag, s.real) * (1j) ** i for s in shape]))\n",
    "            return tuple(res)\n",
    "        res = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    shape = []\n",
    "                    dfs(i, j)\n",
    "                    res.add(standardize(shape))\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pos = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        def dfs(i, j):\n",
    "            vis.add((i, j))\n",
    "            grid[i][j] = 0\n",
    "            for dx, dy in pos:\n",
    "                x, y = i + dx, j + dy \n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:\n",
    "                    dfs(x, y)\n",
    "        \n",
    "        def check():\n",
    "            s = 0\n",
    "            nums = list(vis)\n",
    "            n = len(nums)\n",
    "            d = 0\n",
    "            for i in range(n):\n",
    "                x, y = nums[i]\n",
    "                for j in range(i + 1, n):\n",
    "                    a, b = nums[j]\n",
    "                    d += ((x - a) ** 2 + (y - b) ** 2) ** 0.5\n",
    "            \n",
    "            for x in res:\n",
    "                if abs(d - x) < 1e-5:\n",
    "                    break\n",
    "            else:\n",
    "                res.add(d)\n",
    "        \n",
    "        vis = set()\n",
    "        res = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    dfs(i, j)\n",
    "                    check()\n",
    "                    vis.clear()\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        islands = []  # keep all points of islands in a row\n",
    "        def find_next(r, c, idx):  # DFS to find the island\n",
    "            grid[r][c] = 0\n",
    "            islands[idx].append((r,c))\n",
    "            for i, j in [(-1,0), (1,0), (0,-1), (0,1)]:\n",
    "                if 0 <= r+i < len(grid) and 0 <= c+j < len(grid[0]) and grid[r+i][c+j] == 1:\n",
    "                    find_next(r+i, c+j, idx)\n",
    "\n",
    "        hashed_cache = set()\n",
    "        def add_hash(idx):  # add to hash_cache if uniqe\n",
    "            sig = []\n",
    "            # total 8 ways to reshape\n",
    "            for i, j in [(1,1), (1,-1), (-1,1), (-1,-1)]: \n",
    "                for s in (True, False):\n",
    "                    mnx, mny = inf, inf\n",
    "                    sig = []\n",
    "                    for p in islands[idx]:\n",
    "                        mnx = min(mnx, p[0]*i if s else p[1]*i)\n",
    "                        mny = min(mny, p[1]*j if s else p[0]*j)\n",
    "                    for p in islands[idx]:\n",
    "                        sig.append(((p[0]*i if s else p[1]*i) - mnx, (p[1]*j if s else p[0]*j) - mny))\n",
    "                    sig.sort()  # to build hash signature\n",
    "                    if tuple(sig) in hashed_cache:  # has a shape already in\n",
    "                        return  \n",
    "            hashed_cache.add(tuple(sig))  # no shape found, unique, add\n",
    "        \n",
    "        # find islands\n",
    "        for r in range(len(grid)):\n",
    "            for c in range(len(grid[0])):\n",
    "                if grid[r][c] == 1:\n",
    "                    islands.append([])\n",
    "                    find_next(r, c, len(islands)-1)\n",
    "\n",
    "        # build unique hash\n",
    "        for i in range(len(islands)):\n",
    "            add_hash(i)\n",
    "            \n",
    "        return len(hashed_cache)\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        islands = []\n",
    "        def find_next(r, c, idx):\n",
    "            grid[r][c] = 0\n",
    "            islands[idx].append((r,c))\n",
    "            for i, j in [(-1,0), (1,0), (0,-1), (0,1)]:\n",
    "                if 0 <= r+i < len(grid) and 0 <= c+j < len(grid[0]) and grid[r+i][c+j] == 1:\n",
    "                    find_next(r+i, c+j, idx)\n",
    "\n",
    "        hashed_cache = set()\n",
    "        def add_hash(idx):\n",
    "            sig = []\n",
    "            for i, j in [(1,1), (1,-1), (-1,1), (-1,-1)]:\n",
    "                for s in (True, False):\n",
    "                    mnx, mny = inf, inf\n",
    "                    sig = []\n",
    "                    for p in islands[idx]:\n",
    "                        mnx = min(mnx, p[0]*i if s else p[1]*i)\n",
    "                        mny = min(mny, p[1]*j if s else p[0]*j)\n",
    "                    for p in islands[idx]:\n",
    "                        sig.append(((p[0]*i if s else p[1]*i) - mnx, (p[1]*j if s else p[0]*j) - mny))\n",
    "                    sig.sort()\n",
    "                    if tuple(sig) in hashed_cache:\n",
    "                        return  \n",
    "            hashed_cache.add(tuple(sig))\n",
    "        \n",
    "\n",
    "        for r in range(len(grid)):\n",
    "            for c in range(len(grid[0])):\n",
    "                if grid[r][c] == 1:\n",
    "                    islands.append([])\n",
    "                    find_next(r, c, len(islands)-1)\n",
    "        for i in range(len(islands)):\n",
    "            add_hash(i)\n",
    "        return len(hashed_cache)\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        islands = []\n",
    "        def find_next(r, c, idx):\n",
    "            grid[r][c] = 0\n",
    "            islands[idx].append((r,c))\n",
    "            for i, j in [(-1,0), (1,0), (0,-1), (0,1)]:\n",
    "                if 0 <= r+i < len(grid) and 0 <= c+j < len(grid[0]) and grid[r+i][c+j] == 1:\n",
    "                    find_next(r+i, c+j, idx)\n",
    "\n",
    "        hashed_cache = set()\n",
    "        def add_hash(idx):\n",
    "            sig = []\n",
    "            for i, j in [(1,1), (1,-1), (-1,1), (-1,-1)]:\n",
    "                for s in (True, False):\n",
    "                    mnx, mny = inf, inf\n",
    "                    sig = []\n",
    "                    for p in islands[idx]:\n",
    "                        mnx = min(mnx, p[0]*i if s else p[1]*i)\n",
    "                        mny = min(mny, p[1]*j if s else p[0]*j)\n",
    "                    for p in islands[idx]:\n",
    "                        sig.append(((p[0]*i if s else p[1]*i) - mnx, (p[1]*j if s else p[0]*j) - mny))\n",
    "                    sig.sort()\n",
    "                    if tuple(sig) in hashed_cache:\n",
    "                        return  \n",
    "            hashed_cache.add(tuple(sig))\n",
    "        \n",
    "\n",
    "        for r in range(len(grid)):\n",
    "            for c in range(len(grid[0])):\n",
    "                if grid[r][c] == 1:\n",
    "                    islands.append([])\n",
    "                    find_next(r, c, len(islands)-1)\n",
    "        for i in range(len(islands)):\n",
    "            add_hash(i)\n",
    "        return len(hashed_cache)\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # DFS + Canonical Serialization. Time O(mnlog(mn)) Space O(mn)\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        res = set()\n",
    "        def dfs(x, y):\n",
    "            if grid[x][y] == 0: return\n",
    "            self.island.append((x, y))\n",
    "            grid[x][y] = 0\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    dfs(nx, ny)\n",
    "\n",
    "        # get the canonical serialization of an island\n",
    "        def canonical(island):\n",
    "            # 8 operations allowed:\n",
    "            # (x, y), (-x, y), (x, -y), (-x, -y), (y, x)         , (-y, x), (y, -x), (-y, -x)\n",
    "            # start , ver ref, hor ref, ro 180  , ro 90 & ver ref, ro 270 , ro 90  , ro 270 & ver ref\n",
    "            ops = [(1, 1), (-1, 1), (1, -1), (-1, -1)]\n",
    "            # get all 8 variants of the island\n",
    "            variants = [[] for _ in range(8)]\n",
    "            for i, (opx, opy) in enumerate(ops):\n",
    "                for x, y in island:\n",
    "                    variants[i].append([opx * x, opy * y])\n",
    "                    variants[i+4].append([opx * y, opy * x])\n",
    "            # change the land indices to the relative distance to minx and miny\n",
    "            # imagine use a smallest rectangle to wrap the island, upper-left corner is (minx, miny)\n",
    "            # sort each variant as well\n",
    "            for variant in variants:\n",
    "                minx, miny = min([x for x, _ in variant]), min([y for _, y in variant])\n",
    "                for pos in variant:\n",
    "                    pos[0], pos[1] = pos[0] - minx, pos[1] - miny\n",
    "                variant.sort()\n",
    "            # build the list(list) into tuple(tuple)\n",
    "            return tuple([tuple(pos) for pos in max(variants)])\n",
    "\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] == 1:\n",
    "                    self.island = []\n",
    "                    dfs(x, y)\n",
    "                    res.add(canonical(self.island))\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        res = set()\n",
    "        def dfs(x, y):\n",
    "            if grid[x][y] == 0: return\n",
    "            self.island.append((x, y))\n",
    "            grid[x][y] = 0\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    dfs(nx, ny)\n",
    "\n",
    "        def canonical(island):\n",
    "            ops = [(1, 1), (-1, 1), (1, -1), (-1, -1)]\n",
    "            variants = [[] for _ in range(8)]\n",
    "            for i, (opx, opy) in enumerate(ops):\n",
    "                for x, y in island:\n",
    "                    variants[i].append([opx * x, opy * y])\n",
    "                    variants[i+4].append([opx * y, opy * x])\n",
    "            for variant in variants:\n",
    "                minx, miny = min([x for x, _ in variant]), min([y for _, y in variant])\n",
    "                for pos in variant:\n",
    "                    pos[0], pos[1] = pos[0] - minx, pos[1] - miny\n",
    "                variant.sort()\n",
    "            return tuple([tuple(pos) for pos in max(variants)])\n",
    "\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] == 1:\n",
    "                    self.island = []\n",
    "                    dfs(x, y)\n",
    "                    res.add(canonical(self.island))\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # DFS + Canonical Serialization. Time O(mnlog(mn)) Space O(mn)\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        res = set()\n",
    "        def dfs(x, y):\n",
    "            if grid[x][y] == 0: return\n",
    "            self.island.append((x, y))\n",
    "            grid[x][y] = 0\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    dfs(nx, ny)\n",
    "\n",
    "        # get the canonical serialization of an island\n",
    "        def canonical(island):\n",
    "            # 8 operations allowed:\n",
    "            # (x, y), (-x, y), (x, -y), (-x, -y), (y, x)         , (-y, x), (y, -x), (-y, -x)\n",
    "            # start , ver ref, hor ref, ro 180  , ro 90 & ver ref, ro 270 , ro 90  , ro 270 & ver ref\n",
    "            ops = [(1, 1), (-1, 1), (1, -1), (-1, -1)]\n",
    "            # get all 8 variants of the island\n",
    "            variants = [[] for _ in range(8)]\n",
    "            for i, (opx, opy) in enumerate(ops):\n",
    "                for x, y in island:\n",
    "                    variants[i].append([opx * x, opy * y])\n",
    "                    variants[i+4].append([opx * y, opy * x])\n",
    "            # change the land indices to the relative distance to minx and miny\n",
    "            # imagine use a smallest rectangle to wrap the island, upper-left corner is (minx, miny)\n",
    "            # sort each variant as well\n",
    "            for variant in variants:\n",
    "                minx, miny = min([x for x, _ in variant]), min([y for _, y in variant])\n",
    "                for pos in variant:\n",
    "                    pos[0], pos[1] = pos[0] - minx, pos[1] - miny\n",
    "                variant.sort()\n",
    "            # take the max of variants and build the list(list) into tuple(tuple)\n",
    "            return tuple([tuple(pos) for pos in max(variants)])\n",
    "\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] == 1:\n",
    "                    self.island = []\n",
    "                    dfs(x, y)\n",
    "                    res.add(canonical(self.island))\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0]) \n",
    "        vis = [[0] * n for _ in range(m)]\n",
    "        def dfs(i,j, ans):\n",
    "            vis[i][j] = 1\n",
    "            ans.append((i,j))\n",
    "            for ni,nj in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:\n",
    "                if 0<=ni<m and 0<=nj<n and grid[ni][nj] ==1 and not vis[ni][nj]:\n",
    "                    dfs(ni,nj, ans)\n",
    "        def func(ans):\n",
    "            x1, y1, x2, y2 = m,n,0,0\n",
    "            for x,y in ans:\n",
    "                x1 = min(x1,x)\n",
    "                x2 = max(x2,x)\n",
    "                y1 = min(y1,y)\n",
    "                y2 = max(y2,y) \n",
    "            vec1 = [0] * (x2-x1+1) \n",
    "            vec2 = [0] * (y2-y1+1)\n",
    "            l1, l2 = len(vec1),len(vec2) \n",
    "            diag1 = [0] * (l1 + l2 - 1)\n",
    "            diag2 = [0] * (l1 + l2 - 1)\n",
    "            for x, y in ans:\n",
    "                vec1[x-x1] += 1\n",
    "                vec2[y-y1] += 1\n",
    "                diag1[(x-x1) + (y-y1)] += 1 \n",
    "                diag2[(x-x1) - (y-y1) + l2 - 1] += 1\n",
    "            return tuple(vec1), tuple(vec2), tuple(diag1), tuple(diag2) \n",
    "\n",
    "        arr = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and not vis[i][j]:\n",
    "                    ans = [] \n",
    "                    dfs(i,j, ans) \n",
    "                    row,col,diag1,diag2 = func(ans) \n",
    "                    arr.append((row, col, diag1, diag2)) \n",
    "        l = len(arr)\n",
    "        #print(arr) \n",
    "        def eq(a,b):\n",
    "            return (a == b) or (a == b[::-1])\n",
    "        f = defaultdict(int)  \n",
    "        cnt = 0\n",
    "        for i in range(l):\n",
    "            if arr[i] in f:\n",
    "                continue \n",
    "            cnt += 1\n",
    "            f[arr[i]] = cnt \n",
    "            a1,b1,c1,d1 = arr[i]\n",
    "            for j in range(i+1,l):\n",
    "                if arr[j] not in f:\n",
    "                    a2,b2,c2,d2 = arr[j] \n",
    "                    if (eq(a1,a2) and eq(b1,b2) or eq(a1,b2) and eq(b1,a2)) and \\\n",
    "                    (eq(c1,c2) and eq(d1,d2) or eq(c1,d2) and eq(d1,c2)): \n",
    "                        f[arr[j]] = cnt \n",
    "                        #print(cnt) \n",
    "        return cnt \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        res = set()\n",
    "        def dfs(x, y):\n",
    "            if grid[x][y] == 0: return\n",
    "            self.island.append((x, y))\n",
    "            grid[x][y] = 0\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    dfs(nx, ny)\n",
    "\n",
    "        def canonical(island):\n",
    "            ops = [(1, 1), (-1, 1), (1, -1), (-1, -1)]\n",
    "            variants = [[] for _ in range(8)]\n",
    "            for i, (opx, opy) in enumerate(ops):\n",
    "                for x, y in island:\n",
    "                    variants[i].append([opx * x, opy * y])\n",
    "                    variants[i+4].append([opx * y, opy * x])\n",
    "            for variant in variants:\n",
    "                minx, miny = min([x for x, _ in variant]), min([y for _, y in variant])\n",
    "                for pos in variant:\n",
    "                    pos[0], pos[1] = pos[0] - minx, pos[1] - miny\n",
    "                variant.sort()\n",
    "            return tuple([tuple(pos) for pos in max(variants)])\n",
    "\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] == 1:\n",
    "                    self.island = []\n",
    "                    dfs(x, y)\n",
    "                    res.add(canonical(self.island))\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def normalize(island):\n",
    "            # Create 8 lists to represent the 8 possible transformations: \n",
    "            # 4 for rotation and 4 for reflection.\n",
    "            ways = [[] for _ in range(8)]\n",
    "            for i, j in island:\n",
    "                ways[0].append((i, j))\n",
    "                ways[1].append((i, -j))\n",
    "                ways[2].append((-i, j))\n",
    "                ways[3].append((-i, -j))\n",
    "                ways[4].append((j, i))\n",
    "                ways[5].append((j, -i))\n",
    "                ways[6].append((-j, i))\n",
    "                ways[7].append((-j, -i))\n",
    "            # Sort the coordinates in each transformation.\n",
    "            ways = [sorted(w) for w in ways]\n",
    "            # Normalize each transformation by adjusting its coordinates relative to the first coordinate.\n",
    "            for w in ways:\n",
    "                ref = w[0]\n",
    "                for i in range(len(island)):\n",
    "                    w[i] = (w[i][0] - ref[0], w[i][1] - ref[1])\n",
    "            # Return the lexicographically smallest representation among the 8 transformations.\n",
    "            return tuple(sorted(ways)[0])\n",
    "       \n",
    "        def dfs(i, j):\n",
    "            island.append((i, j))\n",
    "            for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):\n",
    "                x, y = i + dx, j + dy\n",
    "                if 0 <= x < m and 0 <= y < n and (x, y) not in visit and grid[x][y]==1:\n",
    "                    visit.add((x, y))\n",
    "                    dfs(x, y)\n",
    "\n",
    "        visit = set()\n",
    "        islands = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0 or (i, j) in visit:\n",
    "                    continue\n",
    "                island = []\n",
    "                visit.add((i, j))\n",
    "                dfs(i, j)\n",
    "                if island:\n",
    "                    islands.add(normalize(island))\n",
    "        return len(islands)\n",
    "\"\"\"\n",
    "把岛屿坐标,放到坐标系上,然后画一下,求形状, 就是 求坐标间的相对位置. 坐标间相对位置(值)一样,形状就一样.\n",
    "\n",
    "上下翻转:  x 坐标不变, y 坐标取反. (x, y) --> (x, -y)\n",
    "左右翻转: x 坐标取反, y 坐标不变.  (x, y) --> (-x, y)\n",
    "旋转90°:  (x, y) --> (y, -x)\n",
    "旋转180°, 270°:  就是在 旋转90° 后,在旋转1次, 2次.\n",
    "一共8个方向, 然后排序,减去每个岛屿坐标集的里最小值. 就可得其相对自身最小坐标的形状.\n",
    "set() / dict() 去重,就是个数.\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        seen = set()\n",
    "        dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))\n",
    "\n",
    "        def dfs(x, y):\n",
    "            island.append((x, y))\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and (nx, ny) not in seen and grid[nx][ny]==1:\n",
    "                    seen.add((nx, ny))\n",
    "                    dfs(nx, ny)\n",
    "\n",
    "        # Define a function to normalize the coordinates of an island.\n",
    "        # This function ensures that the shape of an island is represented in a unique way, regardless of rotation or reflection.\n",
    "        def normalize(island):\n",
    "            # Create 8 lists to represent the 8 possible transformations: \n",
    "            # 4 for rotation and 4 for reflection.\n",
    "            ways = [[] for _ in range(8)]\n",
    "            for i, j in island:\n",
    "                ways[0].append((i, j))\n",
    "                ways[1].append((i, -j))\n",
    "                ways[2].append((-i, j))\n",
    "                ways[3].append((-i, -j))\n",
    "                ways[4].append((j, i))\n",
    "                ways[5].append((j, -i))\n",
    "                ways[6].append((-j, i))\n",
    "                ways[7].append((-j, -i))\n",
    "            # Sort the coordinates in each transformation.\n",
    "            ways = [sorted(w) for w in ways]\n",
    "            # Normalize each transformation by adjusting its coordinates relative to the first coordinate.\n",
    "            for w in ways:\n",
    "                ref = w[0]\n",
    "                for i in range(len(island)):\n",
    "                    w[i] = (w[i][0] - ref[0], w[i][1] - ref[1])\n",
    "            # Return the lexicographically smallest representation among the 8 transformations.\n",
    "            return tuple(sorted(ways)[0])\n",
    "\n",
    "        islands = set()\n",
    "        for x in range(len(grid)):\n",
    "            for y in range(len(grid[0])):\n",
    "                if grid[x][y] == 0 or (x, y) in seen:\n",
    "                    continue\n",
    "                island = []\n",
    "                seen.add((x, y))\n",
    "                dfs(x, y)\n",
    "                if island:\n",
    "                    islands.add(normalize(island))\n",
    "        return len(islands)\n",
    "\"\"\"\n",
    "把岛屿坐标,放到坐标系上,然后画一下,求形状, 就是 求坐标间的相对位置. 坐标间相对位置(值)一样,形状就一样.\n",
    "\n",
    "上下翻转:  x 坐标不变, y 坐标取反. (x, y) --> (x, -y)\n",
    "左右翻转: x 坐标取反, y 坐标不变.  (x, y) --> (-x, y)\n",
    "旋转90°:  (x, y) --> (y, -x)\n",
    "旋转180°, 270°:  就是在 旋转90° 后,在旋转1次, 2次.\n",
    "一共8个方向, 然后排序,减去每个岛屿坐标集的里最小值. 就可得其相对自身最小坐标的形状.\n",
    "set() / dict() 去重,就是个数.\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        mark = [[0] * n for _ in range(m)]\n",
    "        d = collections.defaultdict(int)\n",
    "        def dfs(x, y):\n",
    "            q = [[x, y]]\n",
    "            mark[x][y] = 1\n",
    "            s = '1'\n",
    "            while q:\n",
    "                i, j = q.pop(0)\n",
    "                if j < n - 1 and mark[i][j+1] == 0 and grid[i][j+1] == 1:\n",
    "                    mark[i][j+1] = 1\n",
    "                    q.append([i,j+1])\n",
    "                    s += '1'\n",
    "                else:\n",
    "                    s += '0'\n",
    "                if i < m - 1 and mark[i+1][j] == 0 and grid[i+1][j] == 1:\n",
    "                    mark[i+1][j] = 1\n",
    "                    q.append([i+1,j])\n",
    "                    s += '1'\n",
    "                else:\n",
    "                    s += '0'\n",
    "                if j > 0 and mark[i][j-1] == 0 and grid[i][j-1] == 1:\n",
    "                    mark[i][j-1] = 1\n",
    "                    q.append([i,j-1])\n",
    "                    s += '1'\n",
    "                else:\n",
    "                    s += '0'\n",
    "                if i > 0 and mark[i-1][j] == 0 and grid[i-1][j] == 1:\n",
    "                    mark[i-1][j] = 1\n",
    "                    q.append([i-1,j])\n",
    "                    s += '1'\n",
    "                else:\n",
    "                    s += '0'\n",
    "            d[s] += 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and mark[i][j] == 0:\n",
    "                    # print('dd')\n",
    "                    dfs(i, j)\n",
    "        # print(d)\n",
    "        return len(d.items())\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        iland=[]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    mx=i\n",
    "                    my=j\n",
    "                    vis=[]\n",
    "                    grid[i][j]==0\n",
    "                    stack=[]\n",
    "                    stack.append([i,j])\n",
    "                    while stack:\n",
    "                        x,y=stack.pop()\n",
    "                        mx=min(mx,x)\n",
    "                        my=min(my,y)\n",
    "                        vis.append([x,y])\n",
    "                        for x1,y1 in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                            if 0<=x1<m and 0<=y1<n and grid[x1][y1]==1:\n",
    "                                grid[x1][y1]=0\n",
    "                                stack.append([x1,y1])\n",
    "                    #print(mx,my)\n",
    "                    for k in range(len(vis)):\n",
    "                        a,b=vis[k]\n",
    "                        a=a-mx\n",
    "                        b=b-my\n",
    "                        vis[k]=[a,b]\n",
    "                    vis.sort()\n",
    "                    if vis not in iland:\n",
    "                        iland.append(vis)\n",
    "        #print(iland)\n",
    "        return len(iland)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        label = 1\n",
    "        dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "\n",
    "        def valid(i, j):\n",
    "            return 0 <= i < m and 0 <= j < n \n",
    "\n",
    "        def bfs(i, j, label):\n",
    "            dq = deque([[i, j]])\n",
    "            grid[i][j] = label\n",
    "            while dq:\n",
    "                for _ in range(len(dq)):\n",
    "                    x, y = dq.popleft()\n",
    "                    for dx, dy in dir:\n",
    "                        nx, ny = x + dx, y + dy \n",
    "                        if valid(nx, ny) and grid[nx][ny] == 1:\n",
    "                            dq.append([nx, ny])\n",
    "                            grid[nx][ny] = label \n",
    "\n",
    "        islands = defaultdict(list)        \n",
    "        seen = set()\n",
    "\n",
    "        def f(L):\n",
    "            res = []\n",
    "            x, y = L[0]\n",
    "            for a, b in L:\n",
    "                res.append(a - x)\n",
    "                res.append(b - y)\n",
    "            return tuple(res)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    label += 1\n",
    "                    bfs(i, j, label)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    islands[grid[i][j]].append([i, j])\n",
    "        for i in range(2, label + 1):\n",
    "            seen.add(f(islands[i]))\n",
    "        return len(seen)            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        label = 1\n",
    "        dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "\n",
    "        def valid(i, j):\n",
    "            return 0 <= i < m and 0 <= j < n \n",
    "\n",
    "        def bfs(i, j, label):\n",
    "            dq = deque([[i, j]])\n",
    "            grid[i][j] = label\n",
    "            while dq:\n",
    "                for _ in range(len(dq)):\n",
    "                    x, y = dq.popleft()\n",
    "                    for dx, dy in dir:\n",
    "                        nx, ny = x + dx, y + dy \n",
    "                        if valid(nx, ny) and grid[nx][ny] == 1:\n",
    "                            dq.append([nx, ny])\n",
    "                            grid[nx][ny] = label \n",
    "\n",
    "        islands = defaultdict(list)        \n",
    "        seen = set()\n",
    "\n",
    "        def f(L):\n",
    "            res = []\n",
    "            x, y = L[0]\n",
    "            for a, b in L:\n",
    "                res.append(a - x)\n",
    "                res.append(b - y)\n",
    "            return tuple(res)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    label += 1\n",
    "                    bfs(i, j, label)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    islands[grid[i][j]].append([i, j])\n",
    "        for i in range(2, label + 1):\n",
    "            seen.add(f(islands[i]))\n",
    "        return len(seen)            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        islands = set()\n",
    "        \n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[i])):\n",
    "                island = []               \n",
    "                front = [(i,j)]\n",
    "                \n",
    "                while front:\n",
    "                    next=[]\n",
    "                    for x,y in front:\n",
    "                        if 0 <= x < len(grid) and 0 <= y < len(grid[x]) and grid[x][y] == 1:\n",
    "                            grid[x][y]=0\n",
    "                            island.append((x-i,y-j))\n",
    "                            \n",
    "                            for m,n in(x+1,y),(x-1,y), (x, y+1), (x, y-1):\n",
    "                                next.append((m,n))\n",
    "                    front = next\n",
    "                    \n",
    "                if island and str(island) not in islands:\n",
    "                    islands.add(str(island))\n",
    "                    \n",
    "                    \n",
    "        return len(islands)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        label = 1\n",
    "        dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "\n",
    "        def valid(i, j):\n",
    "            return 0 <= i < m and 0 <= j < n \n",
    "\n",
    "        def bfs(i, j, label):\n",
    "            dq = deque([[i, j]])\n",
    "            grid[i][j] = label\n",
    "            while dq:\n",
    "                for _ in range(len(dq)):\n",
    "                    x, y = dq.popleft()\n",
    "                    for dx, dy in dir:\n",
    "                        nx, ny = x + dx, y + dy \n",
    "                        if valid(nx, ny) and grid[nx][ny] == 1:\n",
    "                            dq.append([nx, ny])\n",
    "                            grid[nx][ny] = label \n",
    "\n",
    "        islands = defaultdict(list)\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        def cmp(x, y):\n",
    "            dx, dy = y[0][0] - x[0][0], y[0][1] - x[0][1]\n",
    "            ln = len(x)\n",
    "            for i in range(ln):\n",
    "                if y[i][0] - x[i][0] != dx or y[i][1] - x[i][1] != dy:\n",
    "                    return False \n",
    "            return True \n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    label += 1\n",
    "                    bfs(i, j, label)\n",
    "\n",
    "        if label == 1:\n",
    "            return 0\n",
    "        s = [0] * (label + 1)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    s[grid[i][j]] += 1\n",
    "                    islands[grid[i][j]].append([i, j])\n",
    "        cnt = defaultdict(list)\n",
    "        for i in range(2, label + 1):\n",
    "            cnt[s[i]].append(i)\n",
    "        for k, v in cnt.items():\n",
    "            if k == 1:\n",
    "                ans += 1\n",
    "                continue\n",
    "            if len(v) == 1:\n",
    "                ans += 1\n",
    "                continue\n",
    "            tmp = set(v)\n",
    "            ln = len(v)\n",
    "            for i in range(ln - 1):\n",
    "                if v[i] not in tmp:\n",
    "                    continue\n",
    "                for j in range(i + 1, ln):\n",
    "                    if v[j] not in tmp:\n",
    "                        continue\n",
    "                    if cmp(islands[v[i]], islands[v[j]]):\n",
    "                        tmp.remove(v[j])\n",
    "            ans += len(tmp)\n",
    "        return ans \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        label = 1\n",
    "        dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "\n",
    "        def valid(i, j):\n",
    "            return 0 <= i < m and 0 <= j < n \n",
    "\n",
    "        def bfs(i, j, label):\n",
    "            dq = deque([[i, j]])\n",
    "            grid[i][j] = label\n",
    "            while dq:\n",
    "                for _ in range(len(dq)):\n",
    "                    x, y = dq.popleft()\n",
    "                    for dx, dy in dir:\n",
    "                        nx, ny = x + dx, y + dy \n",
    "                        if valid(nx, ny) and grid[nx][ny] == 1:\n",
    "                            dq.append([nx, ny])\n",
    "                            grid[nx][ny] = label \n",
    "\n",
    "        islands = defaultdict(list)        \n",
    "        seen = set()\n",
    "\n",
    "        def f(L):\n",
    "            res = []\n",
    "            x, y = L[0]\n",
    "            for a, b in L:\n",
    "                res.append(a - x)\n",
    "                res.append(b - y)\n",
    "            return tuple(res)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    label += 1\n",
    "                    bfs(i, j, label)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    islands[grid[i][j]].append([i, j])\n",
    "        for i in range(2, label + 1):\n",
    "            seen.add(f(islands[i]))\n",
    "        return len(seen)            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited, islands = set(), set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and (i, j) not in visited:\n",
    "                    lst = []\n",
    "                    queue = [(i, j)]\n",
    "                    while queue:\n",
    "                        c = queue.pop()\n",
    "                        lst.append((c[0] - i, c[1] - j))    # 每个岛屿中陆地坐标均减去第一次遍历到的陆地坐标\n",
    "                        visited.add(c)\n",
    "                        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                            cur = (c[0] + dx, c[1] + dy)\n",
    "                            if 0 <= cur[0] < m and 0 <= cur[1] < n and grid[cur[0]][cur[1]] == 1 and cur not in visited:\n",
    "                                visited.add(cur)\n",
    "                                queue.append(cur)\n",
    "                    islands.add(frozenset(lst))\n",
    "        return len(islands)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class UnionFinder:\n",
    "    def __init__(self, n):\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.rank = [1 for i in range(n)]\n",
    "    \n",
    "    def find(self, x):\n",
    "        if x == self.root[x]:\n",
    "            return x\n",
    "        rootX = self.find(self.root[x])\n",
    "        self.root[x] = rootX\n",
    "        return rootX\n",
    "    \n",
    "    def union(self, x,y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX == rootY:\n",
    "            return \n",
    "        \n",
    "        if self.rank[rootX] > self.rank[rootY]:\n",
    "            self.rank[rootX] += 1\n",
    "            self.root[rootY] = rootX\n",
    "        else:\n",
    "            self.rank[rootY] += 1\n",
    "            self.root[rootX] = rootY\n",
    "\n",
    "class Solution:\n",
    "    def near(self, x, y, m, n):\n",
    "        dirs = [(0, 1), (1,0), (0, -1),(-1, 0)]\n",
    "\n",
    "        ret = []\n",
    "\n",
    "        for d in dirs:\n",
    "            dx,dy = x + d[0], y + d[1]\n",
    "            if dx >= 0 and dx < n and dy >=0 and dy <m:\n",
    "                ret.append([dx, dy])\n",
    "        return ret\n",
    "    \n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        def hash_coord(coordinates, n):\n",
    "            coordinates = sorted(coordinates)\n",
    "            min_coord = min(coordinates)\n",
    "            fst_layer = min_coord // n\n",
    "            base_coordinates = [c - min_coord for c in coordinates]\n",
    "            fat_layer_num = sum([c // n == fst_layer for c in coordinates])\n",
    "            return tuple(base_coordinates + [11 * fat_layer_num])\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        finder = UnionFinder(m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x, y = j, i\n",
    "                if grid[y][x] == 0:\n",
    "                    continue\n",
    "\n",
    "                for npt in self.near(x, y, m, n):\n",
    "                    nx, ny = npt\n",
    "                    if grid[ny][nx] == 1:\n",
    "                        finder.union(y*n+x, ny*n+nx)\n",
    "        \n",
    "        labels = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    labels[finder.find(i *n + j)].append(i*n+j)\n",
    "       \n",
    "        diffs = set()\n",
    "\n",
    "        for v in labels.values():\n",
    "            print(hash_coord(v, n))\n",
    "            diffs.add(hash_coord(v, n))\n",
    "        return len(diffs)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m ,n =len(grid), len(grid[0])\n",
    "        if m==0:\n",
    "            return 0\n",
    "        self.path = \"0\"\n",
    "        res = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    self.path = \"0\"\n",
    "                    self.dfs(grid, i, j, \"0\")\n",
    "                    res.add(self.path)\n",
    "        return len(res)\n",
    "\n",
    "    def dfs(self, grid, row, col, pre_path):\n",
    "        if not 0<= row< len(grid) or not 0<=col<len(grid[0]) or grid[row][col]==0:\n",
    "            return \n",
    "        grid[row][col] =0\n",
    "        self.path+= pre_path\n",
    "        self.dfs(grid, row-1, col, \"1\")\n",
    "        self.dfs(grid, row+1, col, \"2\")\n",
    "        self.dfs(grid, row, col-1, \"3\")\n",
    "        self.dfs(grid, row, col+1, \"4\")\n",
    "        self.path+=\"0\"\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        lists = []\n",
    "        visited = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    lst = []\n",
    "                    queue = [(i, j)]\n",
    "                    while queue:\n",
    "                        cur = queue.pop()\n",
    "                        visited.add(cur)\n",
    "                        lst.append(list(cur))\n",
    "                        grid[cur[0]][cur[1]] = 0\n",
    "                        for dir in [(1, 0), (-1, 0), (0,  1), (0, -1)]:\n",
    "                            if 0 <= cur[0] + dir[0] < m and 0 <= cur[1] + dir[1] < n and grid[cur[0] + dir[0]][cur[1] + dir[1]] == 1:\n",
    "                                if (cur[0] + dir[0], cur[1] + dir[1]) not in visited:\n",
    "                                    visited.add((cur[0] + dir[0], cur[1] + dir[1]))\n",
    "                                    queue.append((cur[0] + dir[0], cur[1] + dir[1]))\n",
    "                    lists.append(lst)\n",
    "        s = set()\n",
    "        for lst in lists:\n",
    "            i, j = lst[0]\n",
    "            for p in lst:\n",
    "                p[0] -= i\n",
    "                p[1] -= j\n",
    "            s.add(str(lst))\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        if len(grid) == 0: return 0\n",
    "        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        parents = dict([\n",
    "            ((i, j), (i, j))\n",
    "            for i in range(m)\n",
    "            for j in range(n)\n",
    "            if grid[i][j] == 1\n",
    "        ])\n",
    "\n",
    "        def find(c):\n",
    "            if parents[c] == c:\n",
    "                return c\n",
    "            p = find(parents[c])\n",
    "            parents[c] = p\n",
    "            return p\n",
    "\n",
    "        def union(c1, c2):\n",
    "            pc1 = parents[c1]\n",
    "            pc2 = parents[c2]\n",
    "            if pc1 != pc2:\n",
    "                parents[pc1] = pc2\n",
    "        # union\n",
    "        for p in parents:\n",
    "            #print(\"==============\")\n",
    "            #print(f\"Point: {p}\")\n",
    "            for d in dirs:\n",
    "                new_p = (p[0] + d[0], p[1] + d[1])\n",
    "                if new_p in parents and find(new_p) != find(p):\n",
    "                    #print(f\"New Point: {new_p}\")\n",
    "                    union(p, new_p)\n",
    "        # group by islands\n",
    "        islands = collections.defaultdict(list)\n",
    "        #print(parents)\n",
    "        for n in parents:\n",
    "            p = find(n)\n",
    "            islands[p].append(n)\n",
    "        #print(islands.values())\n",
    "\n",
    "        distinct_islands = set()\n",
    "        for i in islands.values():\n",
    "            upper_left = min(i)\n",
    "            new_i = str([(p[0] - upper_left[0], p[1] - upper_left[1]) for p in sorted(i)])\n",
    "            distinct_islands.add(new_i)\n",
    "\n",
    "        return len(distinct_islands)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        lists = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    lst = []\n",
    "                    queue = [(i, j)]\n",
    "                    visited = {(i, j)}\n",
    "                    while queue:\n",
    "                        cur = queue.pop()\n",
    "                        lst.append(list(cur))\n",
    "                        grid[cur[0]][cur[1]] = 0\n",
    "                        for dir in [(1, 0), (-1, 0), (0,  1), (0, -1)]:\n",
    "                            if 0 <= cur[0] + dir[0] < m and 0 <= cur[1] + dir[1] < n and grid[cur[0] + dir[0]][cur[1] + dir[1]] == 1:\n",
    "                                if (cur[0] + dir[0], cur[1] + dir[1]) not in visited:\n",
    "                                    visited.add((cur[0] + dir[0], cur[1] + dir[1]))\n",
    "                                    queue.append([cur[0] + dir[0], cur[1] + dir[1]])\n",
    "                    lst.sort()\n",
    "                    lists.append(lst)\n",
    "        s = set()\n",
    "        for lst in lists:\n",
    "            i, j = lst[0]\n",
    "            for p in lst:\n",
    "                p[0] -= i\n",
    "                p[1] -= j\n",
    "            s.add(str(lst))\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        parent = [-1] * (m*n)\n",
    "\n",
    "        def find(node):\n",
    "            if parent[node] != node:\n",
    "                parent[node] = find(parent[node])\n",
    "            return parent[node]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0: continue\n",
    "                parent[i*n+j] = i*n+j\n",
    "                for di, dj in [[-1, 0], [1, 0], [0, 1], [0, -1]]:\n",
    "                    if 0 <= i+di < m and 0 <= j+dj < n and parent[(i+di)*n+(j+dj)] != -1:\n",
    "                        p_1 = find(i*n+j)\n",
    "                        p_2 = find((i+di)*n+(j+dj))\n",
    "                        if p_1 == p_2: continue\n",
    "                        parent[p_1] = p_2\n",
    "        \n",
    "        island = collections.defaultdict(list)\n",
    "        for idx, p in enumerate(parent):\n",
    "            if p == -1: continue\n",
    "            island[find(p)].append(idx)\n",
    "            \n",
    "        diff_island = set()\n",
    "        for land in island.values():\n",
    "            x = land[0]\n",
    "            i = 0\n",
    "            l =[]\n",
    "            while i < len(land):\n",
    "                if x//n*n <= land[i] < x//n*n + n:\n",
    "                    y = land[i] - x\n",
    "                    l.append(y)\n",
    "                    i += 1\n",
    "                else:\n",
    "                    l.append(land[i]-x)\n",
    "                    x = land[i]\n",
    "            diff_island.add(tuple(l))\n",
    "        return len(diff_island)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        parent = [-1] * (m*n)\n",
    "\n",
    "        def find(node):\n",
    "            if parent[node] != node:\n",
    "                parent[node] = find(parent[node])\n",
    "            return parent[node]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0: continue\n",
    "                parent[i*n+j] = i*n+j\n",
    "                for di, dj in [[-1, 0], [1, 0], [0, 1], [0, -1]]:\n",
    "                    if 0 <= i+di < m and 0 <= j+dj < n and parent[(i+di)*n+(j+dj)] != -1:\n",
    "                        p_1 = find(i*n+j)\n",
    "                        p_2 = find((i+di)*n+(j+dj))\n",
    "                        if p_1 == p_2: continue\n",
    "                        parent[p_1] = p_2\n",
    "        \n",
    "        island = collections.defaultdict(list)\n",
    "        for idx, p in enumerate(parent):\n",
    "            if p == -1: continue\n",
    "            # if idx == parent: island[parent].append[idx]\n",
    "            # else:\n",
    "            island[find(p)].append(idx)\n",
    "        diff_island = set()\n",
    "        for land in island.values():\n",
    "            x = land[0]\n",
    "            i = 0\n",
    "            l =[]\n",
    "            while i < len(land):\n",
    "                if x//n*n <= land[i] < x//n*n + n:\n",
    "                    y = land[i] - x\n",
    "                    l.append(y)\n",
    "                    i += 1\n",
    "                else:\n",
    "                    l.append(land[i]-x)\n",
    "                    x = land[i]\n",
    "            diff_island.add(tuple(l))\n",
    "        return len(diff_island)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # do: up, down, left, right: 1, 2, 3, 4, 0 is start dfs\n",
    "        # undo: -1, -2, -3, -4\n",
    "        self.direction = [(0, -1, '1'), (0, 1, '2'), (-1, 0, '3'), (1, 0, '4')]\n",
    "        shape_set = set()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    shape = []\n",
    "                    self.dfs(grid, i, j, '0', shape)\n",
    "                    shape = ','.join(shape)\n",
    "                    shape_set.add(shape)\n",
    "\n",
    "        return len(shape_set)\n",
    "\n",
    "    def dfs(self, grid, x, y, dir_num, shape):\n",
    "        if x >= len(grid) or x < 0 or y >= len(grid[0]) or y < 0:\n",
    "            return\n",
    "        if grid[x][y] != 1:\n",
    "            return\n",
    "        \n",
    "        grid[x][y] = 2\n",
    "        shape.append(dir_num)\n",
    "        for dx, dy, dir_num in self.direction:\n",
    "            self.dfs(grid, x + dx, y + dy, dir_num, shape)\n",
    "        shape.append('-' + dir_num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        islands = set()\n",
    "        def dfs(i,j,id):\n",
    "            if not 0<=i<m or not 0<=j<n or grid[i][j] == 0:\n",
    "                return\n",
    "            grid[i][j] = 0\n",
    "            self.island += str(id)\n",
    "            dfs(i-1,j,1)#上\n",
    "            dfs(i+1,j,2)#下\n",
    "            dfs(i,j-1,3)#左\n",
    "            dfs(i,j+1,4)#右\n",
    "            self.island += str(-id)\n",
    "            return self.island\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    self.island = str()\n",
    "                    dfs(i,j,0)\n",
    "                    islands.add(self.island)\n",
    "\n",
    "        return len(islands)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(i, j, dir):\n",
    "            if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == 1:\n",
    "                grid[i][j] = 0\n",
    "                return dir + dfs(i + 1, j, 'D') + dfs(i - 1, j, 'U') + dfs(i, j + 1, 'R') + dfs(i, j - 1, 'L') + 'END'\n",
    "            return ''\n",
    "        \n",
    "        seen = set()\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    seen.add(dfs(i, j, 'START'))\n",
    "        return len(seen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        if not grid or len(grid) == 0:\n",
    "            return 0\n",
    "        \n",
    "        row, col = len(grid), len(grid[0])\n",
    "        res = 0\n",
    "        self.visited = set()\n",
    "        shape, curShape = [], []\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 1:\n",
    "                    curShape = []\n",
    "                    self.dfs(grid, i, j, i, j, curShape)\n",
    "                    if curShape not in shape:\n",
    "                        res = res + 1\n",
    "                        shape.append(curShape)\n",
    "\n",
    "        return res\n",
    "    \n",
    "    def dfs(self, grid, x0, y0, x, y, curShape):\n",
    "        dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))\n",
    "        grid[x][y] = 2\n",
    "\n",
    "        for d in dirs:\n",
    "            nx, ny = x + d[0], y + d[1]\n",
    "            if self.isValid(grid, nx, ny) and grid[nx][ny] == 1:\n",
    "                curShape.append([x0 - nx, y0 - ny])\n",
    "                self.dfs(grid, x0, y0, nx, ny, curShape)\n",
    "    \n",
    "    def isValid(self, grid, x, y):\n",
    "        return x >= 0 and y >= 0 and x < len(grid) and y < len(grid[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(i, j, pre):\n",
    "            if not 0<=i<m or not 0<=j<n or grid[i][j] ==0:\n",
    "                return \n",
    "            grid[i][j] = 0\n",
    "            self.path += str(pre)\n",
    "            dfs(i, j-1, 1)\n",
    "            dfs(i-1, j, 2)\n",
    "            dfs(i, j+1, 3)\n",
    "            dfs(i+1, j, 4)\n",
    "            self.path += '0'\n",
    "        \n",
    "        self.path = 0\n",
    "        res = set()\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    self.path = '0'\n",
    "                    dfs(i, j, 0)\n",
    "                    res.add(self.path)\n",
    "        return len(res)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        self.m = len(grid)\n",
    "        self.n = len(grid[0])\n",
    "        self.grid = grid\n",
    "        self.set = set()\n",
    "        res = 0\n",
    "        for i in range(self.m):\n",
    "            for j in range(self.n):\n",
    "                if self.grid[i][j] == 1:\n",
    "                    self.str = \"\"\n",
    "                    self.floodFill(i, j, 666)\n",
    "                    if self.str not in self.set:\n",
    "                        res += 1\n",
    "                        self.set.add(self.str)\n",
    "                    print(self.str)  \n",
    "        return res\n",
    "    \n",
    "    def floodFill(self, i, j, dir):\n",
    "        if i < 0 or i >= self.m or j < 0 or j >= self.n:\n",
    "            return\n",
    "        if self.grid[i][j] == 0:\n",
    "            return\n",
    "        self.grid[i][j] = 0\n",
    "        self.str += str(dir) + \",\"\n",
    "        self.floodFill(i - 1, j, 1)\n",
    "        self.floodFill(i + 1, j, 2)\n",
    "        self.floodFill(i, j - 1, 3)\n",
    "        self.floodFill(i, j + 1, 4)\n",
    "        self.str += str(-dir) + \",\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        uf=UnionFind(m*n+1)\n",
    "        island=[]\n",
    "        unique=set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0:\n",
    "                    uf.union(i*n+j,m*n)\n",
    "                    continue\n",
    "                if i<m-1 and grid[i+1][j] == 1:\n",
    "                    uf.union(i*n+j,(i+1)*n+j)\n",
    "                if j<n-1 and grid[i][j+1] == 1:\n",
    "                    uf.union(i*n+j,i*n+j+1)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if uf.find(i*n+j)==i*n+j:\n",
    "                    island.append(i*n+j)\n",
    "                \n",
    "        for a in island:\n",
    "            union=sorted(list(uf.child[a]))\n",
    "            locs=[]\n",
    "            bi=union[0]//n\n",
    "            bj=union[0]%n\n",
    "            for loc in union:\n",
    "                i=loc//n\n",
    "                j=loc%n\n",
    "                locs.append((i-bi,j-bj))\n",
    "            locs=tuple(locs)\n",
    "            unique.add(locs)\n",
    "\n",
    "        #print(unique)\n",
    "        return len(unique)\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,n):\n",
    "        self.father=[i for i in range(n)]\n",
    "        self.size=[1 for i in range(n)]\n",
    "        self.child=[set([i]) for i in range(n)]\n",
    "\n",
    "    def find(self,a):\n",
    "        if self.father[a] != a:\n",
    "            self.father[a]=self.find(self.father[a])\n",
    "        return self.father[a]\n",
    "\n",
    "    def union(self,a,b):\n",
    "        fa,fb=self.find(a),self.find(b)\n",
    "        if fa == fb:\n",
    "            return\n",
    "        if self.size[fa]>self.size[fb]:\n",
    "            self.father[fb]=fa\n",
    "            self.size[fa]+=self.size[fb]\n",
    "            self.child[fa].update(self.child[fb])\n",
    "        else:\n",
    "            self.father[fa]=fb\n",
    "            self.size[fb]+=self.size[fa]\n",
    "            self.child[fb].update(self.child[fa])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pa = list(range(m * n))\n",
    "        def find(x: int) -> int:\n",
    "            if pa[x] != x:\n",
    "                pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "\n",
    "        def union(x: int, y: int) -> None:\n",
    "            pa[find(x)] = find(y)\n",
    "        \n",
    "        cnt = Counter()\n",
    "        directions = [(-1, 0), (0, -1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                cnt[i * n + j] += 1\n",
    "                for di, dj in directions:\n",
    "                    new_i, new_j = i + di, j + dj\n",
    "                    if 0 <= new_i < m and 0 <= new_j < n and grid[new_i][new_j] == 1:\n",
    "                        if find(i * n + j) == find(new_i * n + new_j):\n",
    "                            continue\n",
    "                        tmp = find(new_i * n + new_j)\n",
    "                        union(new_i * n + new_j, i * n + j)\n",
    "                        cnt[i * n + j] += cnt[tmp]\n",
    "                        del cnt[tmp]\n",
    "        items = list(cnt.items())\n",
    "        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        visited = [[0] * n for _ in range(m)]\n",
    "        def dfs(i: int, j: int, x: int, y: int) -> bool:\n",
    "            visited[i][j] = 1\n",
    "            for di, dj in directions:\n",
    "                new_i, new_j = i + di, j + dj\n",
    "                if 0 <= new_i < m and 0 <= new_j < n and visited[new_i][new_j] == 0 and find(new_i * n + new_j) == find(i * n + j):\n",
    "                    new_x, new_y = x + di, y + dj \n",
    "                    if 0 <= new_x < m and 0 <= new_y < n and find(new_x * n + new_y) == find(x * n + y):\n",
    "                        if dfs(new_i, new_j, new_x, new_y) is False:\n",
    "                            return False\n",
    "                    else:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        k = len(items)\n",
    "        ans = k\n",
    "        for i in range(k - 1):\n",
    "            pos_i, size_i = items[i]\n",
    "            for j in range(i + 1, k):\n",
    "                pos_j, size_j = items[j]\n",
    "                if size_j != size_i:\n",
    "                    continue\n",
    "                visited = [[0] * n for _ in range(m)]\n",
    "                if dfs(pos_i // n, pos_i % n, pos_j // n, pos_j % n):\n",
    "                    ans -= 1\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        def dfs(i, j, pre):\n",
    "            if 0 <= i < m and 0 <= j < n and grid[i][j] == 1:\n",
    "                grid[i][j] = 0\n",
    "                self.path += str(pre)\n",
    "                dfs(i+1, j, 1)\n",
    "                dfs(i-1, j, 2)\n",
    "                dfs(i, j+1, 3)\n",
    "                dfs(i, j-1, 4)\n",
    "                self.path += '0'\n",
    "        \n",
    "        res = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                self.path = ''\n",
    "                if grid[i][j] == 1:\n",
    "                    dfs(i, j, '')\n",
    "                    res.add(self.path)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        def dfs(i, j, pre):\n",
    "            if 0 <= i < m and 0 <= j < n and grid[i][j] == 1:\n",
    "                grid[i][j] = 0\n",
    "                self.path += str(pre)\n",
    "                dfs(i+1, j, 1)\n",
    "                dfs(i-1, j, 2)\n",
    "                dfs(i, j+1, 3)\n",
    "                dfs(i, j-1, 4)\n",
    "                self.path += '0'\n",
    "\n",
    "        res = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                self.path = ''\n",
    "                if grid[i][j] == 1:\n",
    "                    dfs(i, j, '')\n",
    "                    res.add(self.path)\n",
    "                    \n",
    "        \n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        def dfs(i, j, pre):\n",
    "            if 0 <= i < m and 0 <= j < n and grid[i][j] == 1:\n",
    "                grid[i][j] = 0\n",
    "                self.path += str(pre)\n",
    "                dfs(i+1, j, 1)\n",
    "                dfs(i-1, j, 2)\n",
    "                dfs(i, j+1, 3)\n",
    "                dfs(i, j-1, 4)\n",
    "                self.path += '0'\n",
    "        res = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                self.path = ''\n",
    "                if grid[i][j] == 1:\n",
    "                    dfs(i, j, '')\n",
    "                    res.add(self.path)\n",
    "\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        def dfs(i, j, pre):\n",
    "            if 0 <= i < m and 0 <= j < n and grid[i][j] == 1:\n",
    "                grid[i][j] = 0\n",
    "                self.path += str(pre)\n",
    "                dfs(i+1, j, 1)\n",
    "                dfs(i-1, j, 2)\n",
    "                dfs(i, j+1, 3)\n",
    "                dfs(i, j-1, 4)\n",
    "                self.path += '0'\n",
    "\n",
    "        res = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                self.path = ''\n",
    "                if grid[i][j] == 1:\n",
    "                    dfs(i, j, '')\n",
    "                    res.add(self.path)\n",
    "        \n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        # 核心思想：一样形状的岛屿，dfs的遍历顺序是一样的\n",
    "        def backtrack(i, j, step):\n",
    "\n",
    "            if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):\n",
    "                return\n",
    "\n",
    "            if grid[i][j] == 0:\n",
    "                return\n",
    "\n",
    "            grid[i][j] = 0\n",
    "            \n",
    "            global order \n",
    "            order = order + [step]\n",
    "\n",
    "            backtrack(i+1, j, 1)\n",
    "            backtrack(i, j+1, 2)\n",
    "            backtrack(i-1, j, 3)\n",
    "            backtrack(i, j-1, 4)\n",
    "\n",
    "            order = order + [-step]\n",
    "    \n",
    "\n",
    "        res = []\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    global order\n",
    "                    order = []\n",
    "                    backtrack(i, j, 0)\n",
    "                    if order not in res:\n",
    "                        res.append(order)\n",
    "        \n",
    "        return len(res)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        def dfs(x, y, cur):\n",
    "            if x < 0 or x >= m or y < 0 or y >= n:\n",
    "                return\n",
    "            \n",
    "            if grid[x][y] != 1:\n",
    "                return\n",
    "            grid[x][y] = 0\n",
    "            cur.append((x, y))\n",
    "            dfs(x+1, y, cur)\n",
    "            dfs(x-1, y, cur)\n",
    "            dfs(x, y+1, cur)\n",
    "            dfs(x, y-1, cur)\n",
    "\n",
    "        def transform(cur):\n",
    "            minX = min([x for x, _ in cur])\n",
    "            minY = min([y for _, y in cur])\n",
    "            transformed = [f'{x-minX},{y-minY}' for x, y in cur]\n",
    "            return ','.join(transformed)\n",
    "\n",
    "        ans = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    cur = []\n",
    "                    dfs(i, j, cur)\n",
    "                    ans.add(transform(cur))\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        #序列化岛屿\n",
    "\n",
    "        n, m = len(grid), len(grid[0])\n",
    "\n",
    "        def dfs(x, y, sequence, dir):\n",
    "            if x < 0 or x >= n or y < 0 or y >= m or grid[x][y] == 0:\n",
    "                return \n",
    "            grid[x][y] = 0\n",
    "            sequence += [f\"{dir},\"]\n",
    "            dfs( x - 1, y, sequence, 1)\n",
    "            dfs( x + 1, y, sequence, 2)\n",
    "            dfs( x, y - 1, sequence, 3)\n",
    "            dfs(x, y + 1, sequence, 4)\n",
    "\n",
    "            sequence += [f\"-{dir},\"]\n",
    "\n",
    "        maps = {}\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    sequence = []\n",
    "                    dfs( i, j, sequence, 666)\n",
    "                    sequence = \"\".join(sequence)\n",
    "                    maps[sequence] = maps.get(sequence, 0) + 1\n",
    "\n",
    "        \n",
    "        return len(maps)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        if not grid or not grid[0]:\n",
    "            return 0\n",
    "        \n",
    "        def dfs(row, col, start_row, start_col, shape):\n",
    "            if not (0 <= row < len(grid) and 0 <= col < len(grid[0]) and grid[row][col]):\n",
    "                return\n",
    "            grid[row][col] = 0\n",
    "            shape.append((row - start_row, col - start_col))\n",
    "            dfs(row + 1, col, start_row, start_col, shape)\n",
    "            dfs(row - 1, col, start_row, start_col, shape)\n",
    "            dfs(row, col - 1, start_row, start_col, shape)\n",
    "            dfs(row, col + 1, start_row, start_col, shape)\n",
    "\n",
    "        shapes = set()\n",
    "        for row in range(len(grid)):\n",
    "            for col in range(len(grid[0])):\n",
    "                if grid[row][col] == 1:\n",
    "                    shape = []\n",
    "                    dfs(row, col, row, col, shape)\n",
    "                    shapes.add(tuple(shape))\n",
    "\n",
    "        return len(shapes)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, g: List[List[int]]) -> int:\n",
    "        m, n = len(g), len(g[0])\n",
    "        dirs = [(-1, 0, \"u\"), (1, 0, \"d\"), (0, -1, \"l\"), (0, 1, \"r\")]\n",
    "        ans = set()\n",
    "\n",
    "        def dfs(x: int, y: int, path: List[str]):\n",
    "            ans = \"\"\n",
    "            for dx, dy, d in dirs:\n",
    "                nx = x + dx\n",
    "                ny = y + dy \n",
    "                if 0 <= nx < m and 0 <= ny < n and g[nx][ny] == 1:\n",
    "                    g[nx][ny] = 0\n",
    "                    path.append(d)\n",
    "                    dfs(nx, ny, path)\n",
    "                    path.append(\"#\")\n",
    "            \n",
    "            return \"\".join(path)\n",
    "        \n",
    "        for i, row in enumerate(g):\n",
    "            for j, x in enumerate(row):\n",
    "                if x:\n",
    "                    g[i][j] = 0\n",
    "                    ans.add(dfs(i, j, []))\n",
    "            \n",
    "        return len(ans)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        self.grid = grid\n",
    "        self.if_visit_grid = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]\n",
    "        self.len_y = len(grid)\n",
    "        self.len_x = len(grid[0])\n",
    "        self.moves = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "        self.cnt_island = 0\n",
    "        self.islands = []\n",
    "        return self.count_island()\n",
    "    \n",
    "    def visit(self, row, col, island):\n",
    "        if row < 0 or row >= self.len_y or col < 0 or col >= self.len_x:\n",
    "            return False\n",
    "\n",
    "        if self.grid[row][col] == 0 or self.if_visit_grid[row][col]:\n",
    "            return False\n",
    "\n",
    "        island.append([row, col])\n",
    "\n",
    "        self.if_visit_grid[row][col] = True\n",
    "\n",
    "        for move in self.moves:\n",
    "            new_row = row + move[0]\n",
    "            new_col = col + move[1]\n",
    "            self.visit(new_row, new_col, island)\n",
    "\n",
    "        return True\n",
    "\n",
    "    def get_islands(self):\n",
    "        island = []\n",
    "        for row in range(self.len_y):\n",
    "            for col in range(self.len_x):\n",
    "                if self.visit(row, col, island):\n",
    "                    island.sort()\n",
    "                    self.islands.append(island)\n",
    "                island = []\n",
    "\n",
    "    def count_island(self):\n",
    "        self.get_islands()\n",
    "        for i in range(len(self.islands)):\n",
    "            st_point = copy.deepcopy(self.islands[i][0])\n",
    "            for point in self.islands[i]:\n",
    "                point[0] = point[0] - st_point[0]\n",
    "                point[1] = point[1] - st_point[1]\n",
    "        ct_islands = []\n",
    "        for island in self.islands:\n",
    "            if island not in ct_islands:\n",
    "                ct_islands.append(island)\n",
    "        return len(ct_islands)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(r, c, d):\n",
    "            if not (0 <= r < m and 0 <= c < n and grid[r][c] == 1):\n",
    "                return \n",
    "            grid[r][c] = 2\n",
    "            path.append(str(d))\n",
    "            dfs(r, c + 1, 1)\n",
    "            dfs(r + 1, c, 2)\n",
    "            dfs(r, c - 1, 3)\n",
    "            dfs(r - 1, c, 4)\n",
    "            path.append(str(-d))\n",
    "        ans = set()\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if grid[r][c] == 1:\n",
    "                    path = []\n",
    "                    dfs(r, c, 666)\n",
    "                    ans.add(''.join(path))\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        def dfs(i, j, grid, dir):\n",
    "            if i < 0 or j < 0 or i >= m or j >= n:\n",
    "                return \n",
    "            if grid[i][j] == 0:\n",
    "                return \n",
    "            grid[i][j] = 0\n",
    "\n",
    "            self.path.append(str(dir))\n",
    "            self.path.append(',')\n",
    "\n",
    "            dfs(i - 1, j, grid, 1)\n",
    "            dfs(i + 1, j, grid, 2)\n",
    "            dfs(i, j - 1, grid, 3)\n",
    "            dfs(i, j + 1, grid, 4)\n",
    "\n",
    "            self.path.append(str(-dir))\n",
    "            self.path.append(',')\n",
    "\n",
    "        island = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    self.path = []\n",
    "                    dfs(i, j, grid, 666)\n",
    "                    island.add(''.join(self.path))\n",
    "        return len(island)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(x, y, aIsland, bx, by):\n",
    "            if x < 0 or x >= n or y < 0 or y >= m: \n",
    "                return\n",
    "            if grid[x][y] == 0: \n",
    "                return\n",
    "            grid[x][y] = 0\n",
    "            aIsland.add((x - bx, y - by))\n",
    "            for dx, dy in [(1, 0), (0, -1), (-1, 0), (0, 1)]:\n",
    "                nx = x + dx\n",
    "                ny = y + dy\n",
    "                dfs(nx, ny, aIsland, bx, by)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    aIsland = set()\n",
    "                    dfs(i, j, aIsland, i, j)\n",
    "                    visited.add(tuple(aIsland))\n",
    "        \n",
    "        return len(visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "DIRECTIONS = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.islands = set()\n",
    "\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        self.islands = set()\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    path = self.dfs(grid, i, j, list())\n",
    "                    self.islands.add(\"#\".join(path))\n",
    "        return len(self.islands)\n",
    "\n",
    "    def dfs(self, grid, i, j, path):\n",
    "        if grid[i][j] == 0:\n",
    "            return path\n",
    "\n",
    "        grid[i][j] = 0\n",
    "        for index, direction in enumerate(DIRECTIONS):\n",
    "            x, y = direction[0] + i, direction[1] + j\n",
    "            m, n = len(grid), len(grid[0])\n",
    "            if x < 0 or x > m - 1 or y < 0 or y > n - 1:\n",
    "                continue\n",
    "            if grid[x][y] == 0:\n",
    "                continue\n",
    "\n",
    "            path.append(\"+%s\" % index)\n",
    "            self.dfs(grid, x, y, path)\n",
    "            path.append(\"-%s\" % index)\n",
    "            \n",
    "        return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 首先，对于形状相同的岛屿，如果从同一起点出发，dfs 函数遍历的顺序肯定是一样的。\n",
    "    # 如果想把岛屿转化成字符串，说白了就是序列化，序列化说白了就是遍历嘛\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        if not grid:\n",
    "            return 0\n",
    "        \n",
    "        path_set = set()\n",
    "\n",
    "        rows = len(grid)\n",
    "        columns = len(grid[0])\n",
    "\n",
    "        for i in range(rows):\n",
    "            for j in range(columns):\n",
    "                if grid[i][j] == 1:\n",
    "                    # 淹掉这个岛屿，同时存储岛屿的序列化结果\n",
    "                    path = []\n",
    "                    self.dfs(grid, i, j, path, 666)\n",
    "                    print(f'path = {path}')\n",
    "                    path_set.add(''.join(path)) \n",
    "\n",
    "        print(f'islands = {path_set}')\n",
    "\n",
    "        # 不相同的岛屿数量\n",
    "        return len(path_set)\n",
    "            \n",
    "\n",
    "    def dfs(self, grid, i, j,path, dir):\n",
    "        rows = len(grid)\n",
    "        columns = len(grid[0])\n",
    "\n",
    "        if i < 0 or j < 0 or i >= rows or j >= columns or grid[i][j] == 0:\n",
    "            return\n",
    "        # 标记当前节点已经被搜索过\n",
    "        grid[i][j] = 0\n",
    "        # 搜素方向，以1,2,3,4来标记上下左右\n",
    "        path.append(str(dir))\n",
    "        path.append(',')\n",
    "            \n",
    "        # 搜索相邻节点\n",
    "        self.dfs(grid, i - 1, j, path, 1) # 上\n",
    "        self.dfs(grid, i + 1, j, path, 2) # 下\n",
    "        self.dfs(grid, i, j - 1, path, 3) # 左\n",
    "        self.dfs(grid, i, j + 1, path, 4) # 右\n",
    "        \n",
    "        # 搜素后，回溯到上一级\n",
    "        path.append(str(-dir))\n",
    "        path.append(',')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.island=set()\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        self.island=set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    path=self.dfs(grid,i,j,[])\n",
    "                    self.island.add('#'.join(path))\n",
    "        return len(self.island)\n",
    "    def dfs(self,grid,i,j,path):\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        if i<0 or i>=m or j<0 or j>=n or grid[i][j]==0:\n",
    "            return path\n",
    "        grid[i][j]=0\n",
    "        dir=[(-1,0),(0,-1),(0,1),(1,0)]\n",
    "        for index,d in enumerate((dir)):\n",
    "            x=i+d[0]\n",
    "            y=j+d[1]\n",
    "            if x<0 or x>=m or y<0 or y>=n or grid[x][y]==0:\n",
    "                continue\n",
    "            path.append('+%s' % index)\n",
    "            self.dfs(grid,x,y,path)\n",
    "            path.append('+%s' % index)\n",
    "        return path\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "DIRECTIONS = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.islands = set()\n",
    "\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        self.islands = set()\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    path = self.dfs(grid, i, j, [])\n",
    "                    self.islands.add(\"\".join(path))\n",
    "        print(self.islands)\n",
    "        return len(self.islands)\n",
    "\n",
    "    def dfs(self, grid, i, j, path):\n",
    "\n",
    "        grid[i][j] = 0\n",
    "        for index, direction in enumerate(DIRECTIONS):\n",
    "            x, y = direction[0] + i, direction[1] + j\n",
    "            m, n = len(grid), len(grid[0])\n",
    "            if x < 0 or x > m - 1 or y < 0 or y > n - 1:\n",
    "                continue\n",
    "            if grid[x][y] == 0:\n",
    "                continue\n",
    "\n",
    "            path.append(\"+%s\" % index)\n",
    "            self.dfs(grid, x, y, path)\n",
    "            path.append(\"-%s\" % index)\n",
    "\n",
    "            \n",
    "        return path\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        #相同：以为遍历顺序相同\n",
    "        #1，2，3，4代表上下左右\n",
    "        ans = set()\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    tmp = []\n",
    "                    self.dfs(grid,i,j,tmp,'0')\n",
    "                    ans.add(\"\".join(tmp))\n",
    "        return len(ans)\n",
    "\n",
    "    def dfs(self,grid,i,j,tmp,dir):\n",
    "        #深度搜索\n",
    "        if i<0 or i>len(grid)-1 or j<0 or j>len(grid[0])-1:\n",
    "            return\n",
    "        if grid[i][j] == 0:\n",
    "            return\n",
    "        grid[i][j] = 0\n",
    "        tmp.append(dir)\n",
    "        self.dfs(grid,i-1,j,tmp,'1')\n",
    "        self.dfs(grid,i+1,j,tmp,'2')\n",
    "        self.dfs(grid,i,j-1,tmp,'3')\n",
    "        self.dfs(grid,i,j+1,tmp,'4')\n",
    "        tmp.append('-')\n",
    "        tmp.append(dir)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "DIRECTIONS = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.islands = set()\n",
    "\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        self.islands = set()\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    path = self.dfs(grid, i, j, list())\n",
    "                    self.islands.add(\"\".join(path))\n",
    "        print(self.islands)\n",
    "        return len(self.islands)\n",
    "\n",
    "    def dfs(self, grid, i, j, path):\n",
    "\n",
    "        grid[i][j] = 0\n",
    "        for index, direction in enumerate(DIRECTIONS):\n",
    "            x, y = direction[0] + i, direction[1] + j\n",
    "            m, n = len(grid), len(grid[0])\n",
    "            if x < 0 or x > m - 1 or y < 0 or y > n - 1:\n",
    "                continue\n",
    "            if grid[x][y] == 0:\n",
    "                continue\n",
    "\n",
    "            path.append(\"+%s\" % index)\n",
    "            self.dfs(grid, x, y, path)\n",
    "            path.append(\"-%s\" % index)\n",
    "\n",
    "            \n",
    "        return path\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(grid, row, col, path, curr):\n",
    "            if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]):\n",
    "                return\n",
    "            if grid[row][col] != 1:\n",
    "                return\n",
    "            \n",
    "            grid[row][col] = 2\n",
    "            \n",
    "            # Update the path\n",
    "            curr.append(path)\n",
    "            \n",
    "            dfs(grid, row+1, col, 'D', curr)\n",
    "            dfs(grid, row-1, col, 'U', curr)\n",
    "            dfs(grid, row, col+1, 'R', curr)\n",
    "            dfs(grid, row, col-1, 'L', curr)\n",
    "            \n",
    "            # To distinguish between different shapes, append a 'B' for backtracking.\n",
    "            curr.append('B')\n",
    "        \n",
    "        unique_shapes = set()\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    curr_path = []\n",
    "                    dfs(grid, i, j, 'O', curr_path)\n",
    "                    # Convert the list of directions into a string and add it to the set.\n",
    "                    unique_shapes.add(''.join(curr_path))\n",
    "                    \n",
    "        return len(unique_shapes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "substring = ''\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(_grid, _i, _j, dir):\n",
    "            m, n = len(_grid), len(_grid[0])\n",
    "\n",
    "            if _i < 0 or _j < 0 or _i >= m or _j >= n or _grid[_i][_j] == 0:\n",
    "                return\n",
    "            \n",
    "            _grid[_i][_j] = 0\n",
    "            \n",
    "            path_signature.append(dir)\n",
    "            \n",
    "            dfs(_grid, _i + 1, _j, 1)\n",
    "            dfs(_grid, _i, _j + 1, 2)\n",
    "            dfs(_grid, _i - 1, _j, 3)\n",
    "            dfs(_grid, _i, _j - 1, 4)\n",
    "\n",
    "            path_signature.append(0)\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        res = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    path_signature = []\n",
    "                    dfs(grid, i, j, 0)\n",
    "                    if path_signature:\n",
    "                        res.add(tuple(path_signature))\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m, n =len(grid), len(grid[0])\n",
    "        self.path = '0'\n",
    "        res = set()  \n",
    "        def dfs(i, j, pre):\n",
    "            if not 0<=i<m or not 0<=j<n or grid[i][j]==0:\n",
    "                return\n",
    "            grid[i][j]=0\n",
    "            self.path += str(pre)\n",
    "            dfs(i, j-1, 1)\n",
    "            dfs(i, j+1, 2) \n",
    "            dfs(i-1, j, 3)\n",
    "            dfs(i+1, j, 4)\n",
    "            self.path += '0'\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    self.path = '0'\n",
    "                    dfs(i, j, 0)\n",
    "                    res.add(self.path)\n",
    "        return len(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        islands = set()\n",
    "\n",
    "        def dfs(i: int, j: int, step: str, steps: List):\n",
    "            if (i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0])):\n",
    "                return\n",
    "            if (grid[i][j] == 0):\n",
    "                return\n",
    "            \n",
    "            grid[i][j] = 0\n",
    "            steps.append(step)\n",
    "\n",
    "            dfs(i-1,j,'u',steps)\n",
    "            dfs(i+1,j,'d',steps)\n",
    "            dfs(i,j-1,'l',steps)\n",
    "            dfs(i,j+1,'r',steps)\n",
    "\n",
    "            steps.append('-')\n",
    "            steps.append(step)\n",
    "\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if (grid[i][j] == 1):\n",
    "                    steps = []\n",
    "                    dfs(i,j,'0',steps)\n",
    "                    islands.add(''.join(steps))\n",
    "\n",
    "        return len(islands)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        # m,n=len(grid),len(grid[0])\n",
    "        # pos=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        # def dfs(x,y):            \n",
    "        #     grid[x][y]=0\n",
    "        #     for i,[dx,dy] in enumerate(pos):\n",
    "        #         xx,yy=x+dx,y+dy\n",
    "        #         nonlocal path\n",
    "        #         # 只要尝试过，就记录方向\n",
    "        #         path+=str(i)\n",
    "        #         if 0<=xx<m and 0<=yy<n and grid[xx][yy]:                    \n",
    "        #             dfs(xx,yy)\n",
    "\n",
    "        # st=set()\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         if grid[i][j]:\n",
    "        #             path=\"\"\n",
    "        #             dfs(i,j)\n",
    "        #             st.add(path)\n",
    "                    \n",
    "        # return len(st)\n",
    "\n",
    "        \n",
    "    #     # temp = []\n",
    "    #     m, n = len(grid), len(grid[0])\n",
    "    #     islands = set() # 记录所有岛屿的序列化结果\n",
    "    #     for i in range(m):\n",
    "    #         for j in range(n):\n",
    "    #             if grid[i][j] == 1: # 如果岛屿是1\n",
    "    #                 # 淹掉这个岛屿，同时存储岛屿的序列化结果\n",
    "    #                 sb = [] # 没有StringBuilder，用数组代替\n",
    "    #                 # 初始的方向可以随便写，不影响正确性\n",
    "    #                 self.dfs(grid, i, j, sb, 666)\n",
    "    #                 islands.add(\"\".join(sb))\n",
    "\n",
    "    #     return len(islands) # 返回不同的岛屿数量\n",
    "\n",
    "    # def dfs(self, grid: List[List[int]], i: int, j: int, sb: List[str], dir: int) -> None:\n",
    "    #     m, n = len(grid), len(grid[0])\n",
    "    #     if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] == 0:\n",
    "    #         return\n",
    "    #     # 前序遍历位置：进入 (i, j)\n",
    "    #     grid[i][j] = 0\n",
    "    #     sb.append(str(dir)).append(',')\n",
    "\n",
    "    #     self.dfs(grid, i - 1, j, sb, 1)  # 上\n",
    "    #     self.dfs(grid, i + 1, j, sb, 2)  # 下\n",
    "    #     self.dfs(grid, i, j - 1, sb, 3)  # 左\n",
    "    #     self.dfs(grid, i, j + 1, sb, 4)  # 右\n",
    "\n",
    "    #     # 后序遍历位置：离开 (i, j)\n",
    "    #     sb.append(str(-dir)).append(',')\n",
    "\n",
    "\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        island = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    # self.dfs(grid, i, j)\n",
    "                    sb = []\n",
    "                    self.dfs(grid, i, j, sb, 666)\n",
    "                    island.add(\"\".join(sb))\n",
    "                    # temp.append(self.dfs(grid, i, j))\n",
    "        return len(island)\n",
    "    \n",
    "    def dfs(self, grid, i, j, sb, dir):\n",
    "        m, n=  len(grid), len(grid[0])\n",
    "        if i <0 or j<0 or i>=m or j>=n:\n",
    "            return None\n",
    "        if grid[i][j] ==0:\n",
    "            return None\n",
    "        grid[i][j]=0\n",
    "        sb.append(str(dir))  # .append(',')\n",
    "        \n",
    "        self.dfs(grid, i+1, j, sb, 1)\n",
    "        self.dfs(grid, i-1, j, sb, 2)\n",
    "        self.dfs(grid, i, j+1, sb, 3)\n",
    "        self.dfs(grid, i, j-1, sb, 4)\n",
    "        sb.append(str(-dir)) # .append(\",\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        res = set()\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    tmp = []\n",
    "                    self.dfs(grid, i,j, 666, tmp)\n",
    "                    res.add(\"\".join(tmp))\n",
    "                    \n",
    "        return len(res)\n",
    "    def dfs(self, grid, r, c, dir, path):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if not 0<=r<m or not 0<=c<n or grid[r][c]==0:\n",
    "            return\n",
    "        grid[r][c]=0\n",
    "        path.append(str(dir))\n",
    "        self.dfs(grid, r-1, c, 1, path)\n",
    "        self.dfs(grid, r+1, c, 2, path)\n",
    "        self.dfs(grid, r, c-1, 3, path)\n",
    "        self.dfs(grid, r, c+1, 4, path)\n",
    "        path.append(str(-dir))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        res = set()\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    temp = []\n",
    "                    self.dfs(grid, i,j, 888, temp)\n",
    "                    res.add(\"\".join(temp))\n",
    "        return len(res)\n",
    "\n",
    "    def dfs(self, grid, r, c, dir, temp):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if not 0<= r<m or not 0<=c<n or grid[r][c]==0:\n",
    "            return\n",
    "        grid[r][c]=0\n",
    "        temp.append(str(dir))\n",
    "        self.dfs(grid, r-1, c, 1, temp)\n",
    "        self.dfs(grid, r+1, c, 2, temp)\n",
    "        self.dfs(grid, r, c-1, 3, temp)\n",
    "        self.dfs(grid, r, c+1, 4, temp)\n",
    "        temp.append(str(-dir))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        #相同：以为遍历顺序相同\n",
    "        #1，2，3，4代表上下左右\n",
    "        ans = set()\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    tmp = []\n",
    "                    self.dfs(grid,i,j,tmp,0)\n",
    "                    print(tmp)\n",
    "                    ans.add(\"\".join(list(map(lambda x:str(x),tmp))))\n",
    "        return len(ans)\n",
    "\n",
    "    def dfs(self,grid,i,j,tmp,dir):\n",
    "        #深度搜索\n",
    "        if i<0 or i>len(grid)-1 or j<0 or j>len(grid[0])-1:\n",
    "            return\n",
    "        if grid[i][j] == 0:\n",
    "            return\n",
    "        grid[i][j] = 0\n",
    "        tmp.append(dir)\n",
    "        self.dfs(grid,i-1,j,tmp,1)\n",
    "        self.dfs(grid,i+1,j,tmp,2)\n",
    "        self.dfs(grid,i,j-1,tmp,3)\n",
    "        self.dfs(grid,i,j+1,tmp,4)\n",
    "        tmp.append(-dir)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        dirs = [\n",
    "            ['a', 0, 1],\n",
    "            ['b', 0, -1],\n",
    "            ['c', 1, 0],\n",
    "            ['d', -1, 0]\n",
    "        ]\n",
    "\n",
    "        def is_inbound(r, c):\n",
    "            return 0 <= r < len(grid) and 0 <= c < len(grid[0])\n",
    "\n",
    "        def dfs(r, c):\n",
    "            if not is_inbound(r, c) or grid[r][c] == 0:\n",
    "                return ''\n",
    "            \n",
    "            grid[r][c] = 0\n",
    "            current_island = ''\n",
    "            for d in dirs:\n",
    "                direction_indicator = d[0]\n",
    "                new_r = r + d[1]\n",
    "                new_c = c + d[2]\n",
    "\n",
    "                current_island += direction_indicator + dfs(new_r, new_c)\n",
    "            \n",
    "            return current_island\n",
    "        \n",
    "        visited = set()\n",
    "\n",
    "        for ii in range(len(grid)):\n",
    "            for jj in range(len(grid[0])):\n",
    "                if grid[ii][jj] == 1:\n",
    "                    visited.add(dfs(ii, jj))\n",
    "        \n",
    "        return len(visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        directions=[(0,1),(1,0),(-1,0),(0,-1)]\n",
    "        def dfs(x,y):\n",
    "            nonlocal path\n",
    "            grid[x][y]=0\n",
    "            for i,(a,b) in enumerate(directions):\n",
    "                xx=x+a\n",
    "                yy=y+b\n",
    "                path+=str(i)\n",
    "                if 0<=xx<m and 0<=yy<n and grid[xx][yy]==1:\n",
    "                    dfs(xx,yy)\n",
    "        vis=set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    path=\"\"\n",
    "                    dfs(i,j)\n",
    "                    vis.add(path)\n",
    "        return len(vis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        def dfs(i, j):\n",
    "            grid[i][j] = 0\n",
    "            for idx, (a, b) in enumerate(pos):\n",
    "                nonlocal path\n",
    "                path += str(idx) # 只要尝试过，就记录方向\n",
    "                # path += '({},{})'.format(a, b)\n",
    "                if 0 <= i+a < m and 0 <= j+b < n and grid[i+a][j+b]:\n",
    "                    dfs(i+a, j+b)\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pos = [(1,0), (-1,0), (0,1), (0,-1)]\n",
    "        res = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                path = ''\n",
    "                if grid[i][j] == 1:\n",
    "                    path = ''\n",
    "                    dfs(i, j)\n",
    "                    res.add(path)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        pos=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        def dfs(x,y):            \n",
    "            grid[x][y]=0\n",
    "            for i,[dx,dy] in enumerate(pos):\n",
    "                xx,yy=x+dx,y+dy\n",
    "                nonlocal path\n",
    "                # 只要尝试过，就记录方向\n",
    "                path+=str(i)\n",
    "                if 0<=xx<m and 0<=yy<n and grid[xx][yy]:                    \n",
    "                    dfs(xx,yy)\n",
    "\n",
    "        st=set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    path=\"\"\n",
    "                    dfs(i,j)\n",
    "                    st.add(path)\n",
    "                    \n",
    "        return len(st)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        pos=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        def dfs(x,y):            \n",
    "            grid[x][y]=0\n",
    "            for i,[dx,dy] in enumerate(pos):\n",
    "                xx,yy=x+dx,y+dy\n",
    "                nonlocal path\n",
    "                # 只要尝试过，就记录方向\n",
    "                path+=str(i)\n",
    "                if 0<=xx<m and 0<=yy<n and grid[xx][yy]:                    \n",
    "                    dfs(xx,yy)\n",
    "\n",
    "        st=set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    path=\"\"\n",
    "                    dfs(i,j)\n",
    "                    st.add(path)\n",
    "                    \n",
    "        return len(st)\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        d=[[1,0],[0,1],[-1,0],[0,-1]]\n",
    "        ls=[]\n",
    "        def dfs(x,y):\n",
    "            if x<0 or y<0 or x>=m or y>=n:\n",
    "                return \n",
    "            if grid[x][y]==0:\n",
    "                return \n",
    "            grid[x][y]=0\n",
    "            k=0\n",
    "            nonlocal count\n",
    "            now=count\n",
    "            count+=1\n",
    "            for dx,dy in d:\n",
    "                #i+=1\n",
    "                if 0<=x+dx<m and 0<=y+dy<n:\n",
    "                    if grid[x+dx][y+dy]==1:\n",
    "                        \n",
    "                        k+=1\n",
    "                        ls.append(str(dx)+str(dy)+str(k)+str(now))\n",
    "                        dfs(x+dx,y+dy)\n",
    "        s=set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                count=0\n",
    "                if grid[i][j]==1:\n",
    "                    ls=[]\n",
    "                    dfs(i,j)\n",
    "                    s.add(\"\".join(ls))\n",
    "        return len(list(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class MEM:\n",
    "    s = []\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        res = set()\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    mem = MEM()\n",
    "                    self.dfs(grid, i, j ,0, mem)\n",
    "                    res.add(\"\".join(mem.s))\n",
    "        return len(res)\n",
    "\n",
    "    \n",
    "    def dfs(self, grid, row, col, dir, mem):\n",
    "        if row < 0 or row >= len(grid) or col <0 or col >=len(grid[0]):\n",
    "            return \n",
    "        if grid[row][col]==0:\n",
    "            return\n",
    "        grid[row][col]=0\n",
    "        mem.s = mem.s + [str(dir)] + [\",\"]\n",
    "        self.dfs(grid, row-1, col, 1, mem)\n",
    "        self.dfs(grid, row+1, col, 2, mem)\n",
    "        self.dfs(grid, row, col-1, 3, mem)\n",
    "        self.dfs(grid, row, col+1, 4, mem)\n",
    "        mem.s = mem.s + [\"-\"] + [str(dir)] + [\",\"]\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class MEM:\n",
    "    s = []\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        res = set()\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    mem = MEM()\n",
    "                    self.dfs(grid, i, j ,0, mem)\n",
    "                    res.add(\"\".join(mem.s))\n",
    "        return len(res)\n",
    "\n",
    "    \n",
    "    def dfs(self, grid, row, col, dir, mem):\n",
    "        if row < 0 or row >= len(grid) or col <0 or col >=len(grid[0]):\n",
    "            return \n",
    "        if grid[row][col]==0:\n",
    "            return\n",
    "        grid[row][col]=0\n",
    "        mem.s = mem.s + [str(dir)] + [\",\"]\n",
    "        self.dfs(grid, row-1, col, 1, mem)\n",
    "        self.dfs(grid, row+1, col, 2, mem)\n",
    "        self.dfs(grid, row, col-1, 3, mem)\n",
    "        self.dfs(grid, row, col+1, 4, mem)\n",
    "        mem.s = mem.s + [\"-\"] + [str(dir)] + [\",\"]\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class MEM:\n",
    "    s = []\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        res = set()\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    mem = MEM()\n",
    "                    self.dfs(grid, i, j ,0, mem)\n",
    "                    res.add(\"\".join(mem.s))\n",
    "        return len(res)\n",
    "\n",
    "    \n",
    "    def dfs(self, grid, row, col, dir, mem):\n",
    "        if row < 0 or row >= len(grid) or col <0 or col >=len(grid[0]):\n",
    "            return \n",
    "        if grid[row][col]==0:\n",
    "            return\n",
    "        grid[row][col]=0\n",
    "        mem.s = mem.s + [str(dir)] + [\",\"]\n",
    "        self.dfs(grid, row-1, col, 1, mem)\n",
    "        self.dfs(grid, row+1, col, 2, mem)\n",
    "        self.dfs(grid, row, col-1, 3, mem)\n",
    "        self.dfs(grid, row, col+1, 4, mem)\n",
    "        mem.s = mem.s + [\"-\"] + [str(dir)] + [\",\"]\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        def dfs(row, col):\n",
    "            if row < 0 or col < 0 or row >= m or col >= n:\n",
    "                return\n",
    "            if visited[row][col]:\n",
    "                return\n",
    "            visited[row][col] = 1\n",
    "            if not grid[row][col]:\n",
    "                return\n",
    "            cur_island.add((row - row_origin, col - col_origin))\n",
    "            dfs(row + 1, col)\n",
    "            dfs(row - 1, col)\n",
    "            dfs(row, col + 1)\n",
    "            dfs(row, col - 1)\n",
    "        \n",
    "        visited = [[0 for i in range(n)] for j in range(m)]\n",
    "        unique_islands = set()\n",
    "        for row in range(m):\n",
    "            for col in range(n):\n",
    "                cur_island = set()\n",
    "                row_origin = row\n",
    "                col_origin = col\n",
    "                dfs(row, col)\n",
    "                if cur_island:\n",
    "                    unique_islands.add(frozenset(cur_island))\n",
    "        \n",
    "        return len(unique_islands)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = \"\" \n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        res = set()\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    self.path = ''\n",
    "                    self.dfs(i, j, '', grid)\n",
    "                    res.add(self.path)\n",
    "        return len(res)\n",
    "\n",
    "    def dfs(self, r, c, id, grid):\n",
    "        if r < 0 or c < 0 or r > len(grid) - 1 or c > len(grid[0]) - 1 or grid[r][c] != 1:\n",
    "            return 0\n",
    "        grid[r][c] = 0\n",
    "        self.path += id\n",
    "        string='abcd'\n",
    "        ind = 0\n",
    "        for dr, dc in ((r-1,c), (r+1,c), (r, c-1), (r, c+1)):\n",
    "            # nr, nc = r + dr, c + dc\n",
    "\n",
    "            self.dfs(dr, dc, string[ind], grid)\n",
    "            ind += 1\n",
    "        # self.dfs(r + 1, c, '1', grid)\n",
    "        # self.dfs(r - 1, c, '2', grid)\n",
    "        # self.dfs(r, c + 1, '3', grid)\n",
    "        # self.dfs(r, c - 1, '4', grid)\n",
    "            self.path += ' '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "       # 执行 DFS 以查找当前岛中的所有单元。\n",
    "       def dfs(row, col, direction):\n",
    "           if row < 0 or col < 0 or row >= len(grid) or col >= len(grid[0]):\n",
    "               return\n",
    "           if (row, col) in seen or not grid[row][col]:\n",
    "               return\n",
    "           seen.add((row, col))\n",
    "           path_signature.append(direction)\n",
    "           dfs(row + 1, col, \"D\")\n",
    "           dfs(row - 1, col, \"U\")\n",
    "           dfs(row, col + 1, \"R\")\n",
    "           dfs(row, col - 1, \"L\")\n",
    "           path_signature.append(\"0\")\n",
    "       \n",
    "       # 只要还有岛屿，就重复启动 DFS。\n",
    "       seen = set()\n",
    "       unique_islands = set()\n",
    "       for row in range(len(grid)):\n",
    "           for col in range(len(grid[0])):\n",
    "                if grid[row][col]:\n",
    "                    path_signature = []\n",
    "                    dfs(row, col, \"0\")\n",
    "                    if path_signature:\n",
    "                        unique_islands.add(tuple(path_signature))\n",
    "       \n",
    "       return len(unique_islands)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        '''\n",
    "        在岛屿数量 (Leetcode200) 的基础上,对走过的路径进行记录 (记录每次探索的方向), 去重之后就是不同的岛屿数量. 详见注释.\n",
    "        '''\n",
    "        n = len(grid)\n",
    "        m = len(grid[0]) if n > 0 else 0\n",
    "        if n * m == 0:\n",
    "            return 0\n",
    "        vis = [[0 for _ in range(m)] for _ in range(n)]\n",
    "\n",
    "        path_set = set()\n",
    "\n",
    "        def dfs(x, y, label, path):\n",
    "            nonlocal vis, n, m, grid\n",
    "            if vis[x][y] > 0:\n",
    "                # 探索过的则不再探索\n",
    "                return\n",
    "            vis[x][y] = label\n",
    "\n",
    "            dx = [0, 1, 0, -1]\n",
    "            dy = [1, 0, -1, 0]\n",
    "\n",
    "            for i in range(4):\n",
    "                nx = x + dx[i]\n",
    "                ny = y + dy[i]\n",
    "                if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 1:\n",
    "                    # 邻居可以拓展则继续拓展\n",
    "                    path.append(i)\n",
    "                    dfs(nx, ny, label, path)\n",
    "                    \n",
    "\n",
    "            # 搜索可以到达的地方, 然后打上标记,\n",
    "            # 不能重新置 0, 因为那样就白走了\n",
    "            # vis[x][y] = 0\n",
    "        \n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if vis[i][j] == 0 and grid[i][j] == 1:\n",
    "                    cnt += 1\n",
    "                    crt_path = [0]\n",
    "                    dfs(i, j, cnt, crt_path)\n",
    "\n",
    "                    # 将路径变为字符串并加入 set\n",
    "                    path_str = '-->'.join([str(i) for i in crt_path])\n",
    "                    path_set.add(path_str)\n",
    "\n",
    "        return len(path_set)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        n, m = len(grid), len(grid[0])\n",
    "        map_copy = [[0] * m for _ in range(n)]\n",
    "        islands = []\n",
    "        def dfs(x, y, map_copy, island):\n",
    "            dirs = [(0, -1), (0, 1), (1, 0), (-1, 0)]\n",
    "            if grid[x][y] == 1 and map_copy[x][y] == 0:\n",
    "                map_copy[x][y] = 1\n",
    "                island.append([x, y])\n",
    "                for d in dirs:\n",
    "                    if 0 <= x + d[0] < n and 0 <= y + d[1] < m:\n",
    "                        dfs(x + d[0], y + d[1], map_copy, island)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1 and map_copy[i][j] == 0:\n",
    "                    island = []\n",
    "                    dfs(i, j, map_copy, island)\n",
    "                    x, y = island[0]\n",
    "                    for z in range(len(island)):\n",
    "                         island[z][0] -= x\n",
    "                         island[z][1] -= y           \n",
    "                    islands.append(island)\n",
    "        res = len(islands)\n",
    "        marks = [0] * len(islands)\n",
    "        def check(i1, i2):\n",
    "            s = set()\n",
    "            if len(i1) != len(i2):\n",
    "                return False\n",
    "            for item in i1:\n",
    "                s.add((item[0], item[1]))\n",
    "            for item in i2:\n",
    "                if (item[0], item[1]) in s:\n",
    "                    s.remove((item[0], item[1]))\n",
    "                else:\n",
    "                    return False\n",
    "            return len(s) == 0\n",
    "        print(islands)\n",
    "        for i in range(len(islands)):\n",
    "            for j in range(i + 1, len(islands)):\n",
    "                if marks[i] == 1:\n",
    "                    continue\n",
    "                if check(islands[i], islands[j]):\n",
    "                    marks[j] = 1\n",
    "                    res -= 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        visited=set()\n",
    "        ans=set()\n",
    "        rds=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        def bfs(x,y):\n",
    "            for rx,ry in rds:\n",
    "                nx,ny=rx+x,ry+y\n",
    "                nk=nx*n+ny\n",
    "                if 0<=nx<m and 0<=ny<n and grid[nx][ny]==1 and nk not in visited:\n",
    "                    visited.add(nk)\n",
    "                    tmp.append((nx,ny))\n",
    "                    bfs(nx,ny)\n",
    "        def findm(tmp):\n",
    "            ri,rj=tmp[0][0],tmp[0][1]\n",
    "            for i,j in tmp:\n",
    "                if i<ri:ri=i\n",
    "                if j<rj: rj =j\n",
    "            return (ri,rj)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                k=i*n+j\n",
    "                if grid[i][j]==1 and k not in  visited:\n",
    "                    visited.add(k)\n",
    "                    tmp=[(i,j)]\n",
    "                    bfs(i,j)\n",
    "                    mi,mj=findm(tmp)\n",
    "                    for ti in range(len(tmp)):\n",
    "                        tx,ty=tmp[ti]\n",
    "                        tmp[ti]=(tx-mi,ty-mj)\n",
    "                    ans.add(tuple(tmp))\n",
    "        # print(ans)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        \n",
    "        def is_unique_island():\n",
    "            for other_island in all_islands:\n",
    "                if len(current_island) != len(other_island):\n",
    "                    continue\n",
    "                for a, b in zip(current_island, other_island):\n",
    "                    if a != b:\n",
    "                        break\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "\n",
    "        def dfs(row, col):\n",
    "            if not 0 <= row < len(grid) or not 0 <= col < len(grid[0]):\n",
    "                return\n",
    "            if grid[row][col] == 0 or (row, col) in seen_grid:\n",
    "                return \n",
    "            seen_grid.append((row, col))\n",
    "            current_island.append((row - ori_row, col - ori_col))\n",
    "            dfs(row, col+1)\n",
    "            dfs(row, col-1)\n",
    "            dfs(row+1, col)\n",
    "            dfs(row-1, col)\n",
    "        \n",
    "        all_islands = []\n",
    "        seen_grid = []\n",
    "        ans = 0\n",
    "\n",
    "        for row in range(len(grid)):\n",
    "            for col in range(len(grid[0])):\n",
    "                if grid[row][col] == 1 and not (row, col) in seen_grid:\n",
    "                    current_island = []\n",
    "                    ori_row, ori_col = row, col\n",
    "                    dfs(row, col)\n",
    "                    if is_unique_island():\n",
    "                        ans += 1\n",
    "                        all_islands.append(current_island)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        Row, Col = len(grid), len(grid[0])\n",
    "        visited = [[False for _ in range(Col)] for _ in range(Row)]\n",
    "\n",
    "        def dfs(r: int, c: int) -> None:\n",
    "            if visited[r][c] == True:\n",
    "                return \n",
    "            visited[r][c] = 1\n",
    "\n",
    "            nxt = [(r, c+1), (r+1, c), (r, c-1), (r-1, c)]\n",
    "            for i in range(4):\n",
    "                nr,nc = nxt[i]\n",
    "                if 0<= nr < Row and 0<= nc < Col and grid[nr][nc]==1:\n",
    "                    self.path += str(i + 1)\n",
    "                    dfs(nr, nc)\n",
    "\n",
    "        rec = set()\n",
    "\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 1 and visited[r][c] == False:\n",
    "                    self.path = \"0\"\n",
    "                    dfs(r, c)\n",
    "                    rec.add(self.path)\n",
    "\n",
    "        return len(rec)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        ans = []\n",
    "        def search(x, y, temp):\n",
    "            for [xx, yy] in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:\n",
    "                if 0<=xx<n and 0<=yy<m and grid[xx][yy] == 1:\n",
    "                    grid[xx][yy] = 2\n",
    "                    temp.append([xx, yy])\n",
    "                    search(xx, yy, temp)\n",
    "            return temp\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    island = []\n",
    "                    island = search(i, j, island)\n",
    "                    ans.append(island)\n",
    "        fin_ans = set()\n",
    "        for j in range(len(ans)):\n",
    "            for i in range(1, len(ans[j])):\n",
    "                ans[j][i][0] = ans[j][i][0] - ans[j][0][0]\n",
    "                ans[j][i][1] = ans[j][i][1] - ans[j][0][1]\n",
    "            if ans[j]:\n",
    "                ans[j][0] = [0, 0]\n",
    "            ans[j] = [tuple(x) for x in ans[j]]\n",
    "            if tuple(ans[j]) not in fin_ans:\n",
    "                fin_ans.add(tuple(ans[j]))\n",
    "        return(len(fin_ans))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        st=set()\n",
    "        \n",
    "        def dfs(x,y):\n",
    "            grid[x][y]=0\n",
    "            for i ,(nx,ny) in enumerate([(x+1,y),(x-1,y),(x,y+1),(x,y-1)]):\n",
    "                nonlocal path\n",
    "                path+=str(i)\n",
    "                if 0<=nx<m and 0<=ny<n and grid[nx][ny]==1:\n",
    "                    dfs(nx, ny)\n",
    "\n",
    "\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    path=\"\"\n",
    "                    dfs(i, j)\n",
    "                    st.add(path)\n",
    "        return len(st)\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        visited = set()\n",
    "        diff_island = set()\n",
    "\n",
    "        def dfs(x, y, direction):\n",
    "            if x < 0 or x >= m or y < 0 or y >= n:\n",
    "                return\n",
    "            if (x, y) in visited or grid[x][y] != 1:\n",
    "                return\n",
    "            \n",
    "            visited.add((x, y))\n",
    "            path.append(direction)\n",
    "            dfs(x+1, y, 'd')\n",
    "            dfs(x-1, y, 'u')\n",
    "            dfs(x, y+1, 'r')\n",
    "            dfs(x, y-1, 'l')\n",
    "            path.append('0')\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    path = []\n",
    "                    dfs(i, j, '0')\n",
    "                    # print(path)\n",
    "                    if path:\n",
    "                        diff_island.add(''.join(path))\n",
    "        # print(diff_island)\n",
    "        return len(diff_island)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        count = {}\n",
    "        colors = {}\n",
    "        def visit(i, j, fa):\n",
    "            if i < 0 or i >= m:\n",
    "                return\n",
    "            if j < 0 or j >= n:\n",
    "                return\n",
    "            if grid[i][j] != 1:\n",
    "                return\n",
    "            if i in colors and j in colors[i]:\n",
    "                return\n",
    "            if not i in colors:\n",
    "                colors[i] = {}\n",
    "            colors[i][j] = fa\n",
    "            if not fa in count:\n",
    "                count[fa] = []\n",
    "            count[fa].append((i, j))\n",
    "            visit(i - 1, j, fa)\n",
    "            visit(i + 1, j, fa)\n",
    "            visit(i, j - 1, fa)\n",
    "            visit(i, j + 1, fa)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                visit(i, j, i*n + j)\n",
    "\n",
    "        def isSame(a, b):\n",
    "            if len(count[a]) != len(count[b]):\n",
    "                return False\n",
    "            x1, y1 = a // n, a % n\n",
    "            x2, y2 = b // n, b % n\n",
    "            #print(x1, y1, x2, y2)\n",
    "            for va in count[a]:\n",
    "                vb = (va[0] - x1 + x2, va[1] - y1 + y2)\n",
    "                #print(\"check\", va, vb)\n",
    "                if vb not in count[b]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        ans = len(count)\n",
    "        countKeys = list(count.keys())\n",
    "        countKeys.sort()\n",
    "        isOut = {}\n",
    "        #print(countKeys)\n",
    "        for i in range(len(countKeys)):\n",
    "            if i in isOut:\n",
    "                continue\n",
    "            for j in range(i + 1, len(countKeys)):\n",
    "                if j in isOut:\n",
    "                    continue\n",
    "                if isSame(countKeys[i], countKeys[j]):\n",
    "                    isOut[j] = 1\n",
    "                    ans -=1\n",
    "        return ans\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        tag = [[0] * n for _ in range(m)]\n",
    "\n",
    "        def fill_all(shape, i, j):\n",
    "            tag[i][j] = 1\n",
    "            directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "            for diff_i, diff_j in directions:\n",
    "                new_i, new_j = i + diff_i, j + diff_j\n",
    "                if [new_i, new_j] not in shape and 0 <= new_i < m and 0 <= new_j < n and grid[new_i][new_j] == 1:\n",
    "                    shape.append([new_i, new_j])\n",
    "                    shape = fill_all(shape, new_i, new_j)\n",
    "            return shape\n",
    "\n",
    "        shapes_list = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                elif tag[i][j] == 0:\n",
    "                    shape = fill_all([[i, j]], i, j)\n",
    "                    shape_diff = [[cur[0] - i, cur[1] - j] for cur in shape]\n",
    "                    if shape_diff not in shapes_list:\n",
    "                        shapes_list.append(shape_diff)\n",
    "\n",
    "        return len(shapes_list)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        def dfs(i:int,j:int)->None:\n",
    "            if i>=m or i<0 or j>=n or j<0: return\n",
    "            if not grid[i][j] or (i,j) in visit: return\n",
    "            s.add((i-origin_i,j-origin_j))\n",
    "            visit.add((i,j))\n",
    "            dfs(i+1, j)\n",
    "            dfs(i-1, j)\n",
    "            dfs(i, j+1)\n",
    "            dfs(i, j-1)\n",
    "        visit = set()\n",
    "        has = set()\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                origin_i,origin_j = i,j\n",
    "                s = set()\n",
    "                dfs(i, j)\n",
    "                if not s: continue\n",
    "                s = frozenset(s)\n",
    "                if s not in has:\n",
    "                    res+=1\n",
    "                    has.add(s)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def dfs(self, x, y, path, grid, k):\n",
    "        \n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        if (x < 0 or x >= m or y < 0 or y >= n):\n",
    "            return\n",
    "        \n",
    "        if grid[x][y] == 1:\n",
    "            grid[x][y] = 0\n",
    "        else:\n",
    "            return\n",
    "        # print(f\"visiting ({x,y})\")\n",
    "        # path.append((x,y))\n",
    "        direction = [[1,0],[-1,0],[0,1],[0,-1]]\n",
    "        path.append(\"0\")\n",
    "\n",
    "        for k in range(4):\n",
    "            nx = x + direction[k][0]\n",
    "            ny = y + direction[k][1]\n",
    "            if k == 0: # 下\n",
    "                path.append(\"2\") \n",
    "            elif k == 1: # 上\n",
    "                path.append(\"1\")\n",
    "            elif k == 2: # 右\n",
    "                path.append(\"4\")\n",
    "            elif k == 3: # 左\n",
    "                path.append(\"3\")\n",
    "            \n",
    "            self.dfs(nx,ny, path,grid, k)\n",
    "\n",
    "            if k == 0: # 下\n",
    "                path.append(\"-2\") \n",
    "            elif k == 1: # 上\n",
    "                path.append(\"-1\")\n",
    "            elif k == 2: # 右\n",
    "                path.append(\"-4\")\n",
    "            elif k == 3: # 左\n",
    "                path.append(\"-3\")\n",
    "\n",
    "        \n",
    "        \n",
    "    def isSame(self, a, b):\n",
    "        if len(a)!=len(b):\n",
    "            return False\n",
    "\n",
    "        i = 0\n",
    "        d = a[0]-b[0]\n",
    "        \n",
    "        for i in range(1, len(a)):\n",
    "            d_curr = a[i]-b[i]\n",
    "            if d_curr != d:\n",
    "                print(f\"a[i] {a[i]}, b[i] {b[i]} different\")\n",
    "                return False\n",
    "        \n",
    "        print(f\"a[i] {a[i]}, b[i] {b[i]} same\")\n",
    "\n",
    "        return True\n",
    "        \n",
    "\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        \n",
    "\n",
    "        islands = {}\n",
    "        path = []\n",
    "        num_island = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                path = []\n",
    "                if grid[i][j] == 1:\n",
    "                    self.dfs(i,j,path,grid, 0)\n",
    "                    num_island += 1\n",
    "                #print(path)\n",
    "                str_path = \"\".join(path)\n",
    "                islands[str_path] = islands.get(str_path,0)+1\n",
    "        \n",
    "        print(islands)\n",
    "        num_same = 0\n",
    "        for key in islands.keys():\n",
    "            if key != \"\":\n",
    "                num_same += islands[key]-1\n",
    "\n",
    "        return num_island-num_same"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        def current_island_is_unique():\n",
    "           for other_island in unique_islands:\n",
    "               if len(other_island) != len(current_island):\n",
    "                   continue\n",
    "               for cell_1, cell_2 in zip(current_island, other_island):\n",
    "                   if cell_1 != cell_2:\n",
    "                       break\n",
    "               else:\n",
    "                   return False\n",
    "           return True\n",
    "           \n",
    "       # 执行 DFS 以查找当前岛中的所有单元。\n",
    "        def dfs(row, col):\n",
    "           if row < 0 or col < 0 or row >= len(grid) or col >= len(grid[0]):\n",
    "               return\n",
    "           if (row, col) in seen or not grid[row][col]:\n",
    "               return\n",
    "           seen.add((row, col))\n",
    "           current_island.append((row - row_origin, col - col_origin))\n",
    "           dfs(row + 1, col)\n",
    "           dfs(row - 1, col)\n",
    "           dfs(row, col + 1)\n",
    "           dfs(row, col - 1)\n",
    "       \n",
    "        # 只要还有岛屿，就重复启动 DFS。\n",
    "        seen = set()\n",
    "        unique_islands = []\n",
    "        for row in range(len(grid)):\n",
    "            for col in range(len(grid[0])):\n",
    "                current_island = []\n",
    "                row_origin = row\n",
    "                col_origin = col\n",
    "                dfs(row, col)\n",
    "                if not current_island or not current_island_is_unique():\n",
    "                    continue\n",
    "                unique_islands.append(current_island)\n",
    "        return len(unique_islands)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "\n",
    "        blocks = []\n",
    "        block = []\n",
    "        block_ori_i = block_ori_j = -1\n",
    "        def dfs(i: int, j: int):\n",
    "            visited[i][j] = True\n",
    "            block.append([i - block_ori_i, j - block_ori_j])\n",
    "            neighbor = [\n",
    "                [i - 1, j],\n",
    "                [i + 1, j],\n",
    "                [i, j - 1],\n",
    "                [i, j + 1],\n",
    "            ]\n",
    "            for pi, pj in neighbor:\n",
    "                if 0 <= pi < m and 0 <= pj < n and grid[pi][pj] == 1 and not visited[pi][pj]:\n",
    "                    dfs(pi, pj)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and not visited[i][j]:\n",
    "                    block = []\n",
    "                    block_ori_i = i\n",
    "                    block_ori_j = j\n",
    "                    dfs(i, j)\n",
    "                    if block not in blocks:\n",
    "                        blocks.append(block.copy())\n",
    "        \n",
    "        # print(blocks)\n",
    "        # 收缩形状  又回去旧思想了...\n",
    "        # 然后合并形状\n",
    "        return len(blocks)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        return self.answer_1(grid)\n",
    "\n",
    "    def answer_1(self, grid):\n",
    "        row_len = len(grid)\n",
    "        col_len = len(grid[0])\n",
    "\n",
    "        def _dfs(row, col, origin_row, origin_col, result):\n",
    "            if row < 0 or col < 0 or row >= row_len or col >= col_len:\n",
    "                return\n",
    "\n",
    "            if (row, col) in seen or grid[row][col] == 0:\n",
    "                return\n",
    "            result.add((row - origin_row, col - origin_col))\n",
    "            seen.add((row, col))\n",
    "\n",
    "            _dfs(row + 1, col, origin_row, origin_col, result)\n",
    "            _dfs(row - 1, col, origin_row, origin_col, result)\n",
    "            _dfs(row, col + 1, origin_row, origin_col, result)\n",
    "            _dfs(row, col - 1, origin_row, origin_col, result)\n",
    "\n",
    "        seen = set()\n",
    "        unique_islands = set()\n",
    "        for row in range(row_len):\n",
    "            for col in range(col_len):\n",
    "                current_island = set()\n",
    "                row_origin = row\n",
    "                col_origin = col\n",
    "\n",
    "                _dfs(row, col, row_origin, col_origin, current_island)\n",
    "\n",
    "                if current_island:\n",
    "                    unique_islands.add(frozenset(current_island))\n",
    "\n",
    "        return len(unique_islands)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        visited = set()\n",
    "        def dfs(row, col):\n",
    "            if (row < 0 or row >= m) or (col < 0 or col >= n):\n",
    "                return\n",
    "            \n",
    "            if (row, col) in visited or grid[row][col] == 0:\n",
    "                return\n",
    "            visited.add((row, col))\n",
    "            currIsland.add((row - row_origin, col - col_origin))\n",
    "            dfs(row + 1, col)\n",
    "            dfs(row - 1, col)\n",
    "            dfs(row, col + 1)\n",
    "            dfs(row, col - 1)\n",
    "        \n",
    "        uniqueIsland = set()\n",
    "        for row in range(m):\n",
    "            for col in range(n):\n",
    "                currIsland = set()\n",
    "                row_origin = row\n",
    "                col_origin = col\n",
    "                dfs(row, col)\n",
    "                if currIsland:\n",
    "                    uniqueIsland.add(frozenset(currIsland))\n",
    "        return len(uniqueIsland)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "       # 执行 DFS 以查找当前岛中的所有单元。\n",
    "       def dfs(row, col):\n",
    "           if row < 0 or col < 0 or row >= len(grid) or col >= len(grid[0]):\n",
    "               return\n",
    "           if (row, col) in seen or not grid[row][col]:\n",
    "               return\n",
    "           seen.add((row, col))\n",
    "           current_island.add((row - row_origin, col - col_origin))\n",
    "           dfs(row + 1, col)\n",
    "           dfs(row - 1, col)\n",
    "           dfs(row, col + 1)\n",
    "           dfs(row, col - 1)\n",
    "       \n",
    "       # 只要还有岛屿，就重复启动 DFS。\n",
    "       seen = set()\n",
    "       unique_islands = set()\n",
    "       for row in range(len(grid)):\n",
    "           for col in range(len(grid[0])):\n",
    "               current_island = set()\n",
    "               row_origin = row\n",
    "               col_origin = col\n",
    "               dfs(row, col)\n",
    "               if current_island:\n",
    "                   unique_islands.add(frozenset(current_island))\n",
    "       \n",
    "       return len(unique_islands)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numDistinctIslands(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "\n",
    "        blocks = []\n",
    "        block = []\n",
    "        block_ori_i = block_ori_j = -1\n",
    "        def dfs(i: int, j: int):\n",
    "            visited[i][j] = True\n",
    "            block.append([i - block_ori_i, j - block_ori_j])\n",
    "            neighbor = [\n",
    "                [i - 1, j],\n",
    "                [i + 1, j],\n",
    "                [i, j - 1],\n",
    "                [i, j + 1],\n",
    "            ]\n",
    "            for pi, pj in neighbor:\n",
    "                if 0 <= pi < m and 0 <= pj < n and grid[pi][pj] == 1 and not visited[pi][pj]:\n",
    "                    dfs(pi, pj)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and not visited[i][j]:\n",
    "                    block = []\n",
    "                    block_ori_i = i\n",
    "                    block_ori_j = j\n",
    "                    dfs(i, j)\n",
    "                    if block not in blocks:\n",
    "                        blocks.append(block.copy())\n",
    "        \n",
    "        print(blocks)\n",
    "        # 收缩形状\n",
    "        # 然后合并形状\n",
    "        return len(blocks)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
